poj 2492 A Bug's Life (并查集)

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cstdlib>
 5 #include <algorithm>
 6 using namespace std;
 7 const int maxn = 2010;
 8 int bin[maxn], op[maxn], n;
 9 void init()
10 {
11     for(int i = 1; i <= n; i++)
12     {
13         bin[i] = i;
14         op[i] = 0;
15     }
16 }
17 int find(int x)
18 {
19     int r, i, j;
20     r =  x;
21     while(r != bin[r])
22         r = bin[r];
23     i = x;
24     while(bin[i] != r)
25     {
26         j = bin[i];
27         bin[i] = r;
28         i = j;
29     }
30     return r;
31 }
32 
33 void merge(int x, int y)
34 {
35     int fx, fy;
36     fx = find(x);
37     fy = find(y);
38     if(fx != fy)
39         bin[fx] = fy;
40 }
41 int main()
42 {
43     int t, m, a, b, f, cou=1;
44     scanf("%d", &t);
45     while(t--)
46     {
47         f = 0;
48         scanf("%d%d", &n, &m);
49         init();
50 
51         while(m--)
52         {
53             scanf("%d%d",&a, &b);
54             if(find(a) == find(b))
55                 f = 1;
56             if(f == 0)
57             {
58                 if(op[a] == 0)
59                     op[a] = b;
60                 else
61                     merge(op[a],b);
62                 if(op[b] == 0)
63                     op[b] =a;
64                 else
65                     merge(op[b],a);
66             }
67         }
68         printf("Scenario #%d:
", cou++);
69         if(f)
70             printf("Suspicious bugs found!

");
71         else
72             printf("No suspicious bugs found!

");
73     }
74     return 0;
75 }