C++ 带权边集法
#include <iostream>
#include <cstring>
#include <unordered_map>
using namespace std;
const int N = 20010;
int p[N], d[N];
int n, m;
unordered_map<int, int> S;
int get(int x)
{
if(S.count(x) == 0) S[x] = n ++;
return S[x];
}
int find(int x)
{
if(p[x] != x)
{
int root = find(p[x]);
d[x] ^= d[p[x]];
p[x] = root;
}
return p[x];
}
int main()
{
cin >> n >> m;
n = 0;
int res = m;
for(int i = 1; i <= m * 2; i ++) p[i] = i;
for(int i = 0; i < m; i ++)
{
int a, b;
string type;
cin >> a >> b >> type;
a = get(a - 1), b = get(b);
int t = 0;
if(type == "odd") t = 1;
int pa = find(a), pb = find(b);
if(pa == pb)
{
if(d[a] ^ d[b] != t)
{
res = i;
break;
}
}
else
{
p[pa] = pb;
d[pa] = d[a] ^ d[b] ^ t;
}
}
cout << res << endl;
return 0;
}
扩展域法
#include <iostream>
#include <cstring>
#include <unordered_map>
using namespace std;
const int N = 20010, BASE = N / 2;
int p[N];
int n, m;
unordered_map<int, int> S;
int get(int x)
{
if(S.count(x) == 0) S[x] = ++ n;
return S[x];
}
int find(int x)
{
if(p[x] != x) p[x] = find(p[x]);
return p[x];
}
int main()
{
cin >> n >> m;
n = 0;
int res = m;
for(int i = 1; i < N; i ++) p[i] = i;
for(int i = 0; i < m; i ++)
{
int a, b;
string type;
cin >> a >> b >> type;
a = get(a - 1), b = get(b);
if(type == "even")
{
if(find(a + BASE) == find(b))
{
res = i;
break;
}
p[find(a)] = find(b);
p[find(a + BASE)] = find(b + BASE);
}
else
{
if(find(a) == find(b))
{
res = i;
break;
}
p[find(a)] = find(b + BASE);
p[find(a + BASE)] = find(b);
}
}
cout << res << endl;
return 0;
}
java 扩展域
import java.util.*;
public class Main {
static int N = 20010, base = N / 2;
static int[] p = new int[N];
static int n, m;
static Map<Integer, Integer> map = new HashMap<Integer, Integer>();
public static int get(int x) {
if(map.containsKey(x) != true) map.put(x, ++ n);
return map.get(x);
}
public static int find(int x) {
if(p[x] != x) p[x] = find(p[x]);
return p[x];
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
n = 0;
int res = m;
for(int i = 0; i < N; i ++) p[i] = i;
for(int i = 0; i < m; i ++) {
int a = sc.nextInt();
int b = sc.nextInt();
String type = sc.next();
a = get(a - 1);
b = get(b);
if("even".equals(type)) {
if(find(a + base) == find(b)) {
res = i;
break;
}
p[find(a)] = find(b);
p[find(a + base)] = find(b + base);
}
else {
if(find(a) == find(b)) {
res = i;
break;
}
p[find(a + base)] = find(b);
p[find(a)] = find(b + base);
}
}
System.out.println(res);
}
}