PS: 开始我用二分染色做了一下这道题目, 今天再用并查集解此题，
POJ 2492 A Bugs Life
。 关键是表示二元关系。?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include
#include
#include
#include
using namespace std;
const int maxn = 2010;
int f[maxn];
int mark[maxn];
int n, m;
bool flag;
//Accepted 676K 750MS G++ 1230B 2014-05-07 20:02:20
int getFather(int x) {
if(x==f[x]) return x;
int t = f[x];
f[x] = getFather(f[x]);
mark[x] = (mark[x]+mark[t])%2;
return f[x];
}
void make(int a, int b) {
int t1 = getFather(a);
int t2 = getFather(b);
if(t1 != t2) {
f[t1] = t2;
if((mark[a]+mark[b])%2==0) {
mark[t1] = 1;
}
}
else {
if(mark[a]==mark[b]) {
flag = false;
}
}
}
int main()
{
int x, y;
int T;
scanf("%d", &T);
for(int t = 1; t <= T; t++) {
scanf("%d%d", &n, &m);
memset(mark, 0, sizeof(mark));
flag = true;
for(int i = 1; i <= n; i++) f[i] = i;
for(int i = 0; i < m; i++) {
scanf("%d%d", &x, &y);
make(x, y);
}
printf("Scenario #%d:\n", t);
if(flag) {
printf("No suspicious bugs found!\n");
} else {
printf("Suspicious bugs found!\n");
}
printf("\n");
}
return 0;
}