poj 1703 Find them, Catch them（并查集）

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cstdlib>
 5 #include <algorithm>
 6 using namespace std;
 7 const int maxn = 100010;
 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;
44     char ch;
45     scanf("%d", &t);
46     while(t--)
47     {
48         scanf("%d%d", &n, &m);
49         init();
50 
51         while(m--)
52         {
53            getchar();
54            scanf("%c%d%d",&ch, &a, &b);
55            if(ch == ‘A‘)
56            {
57                int x, y;
58                x = find(a);
59                y = find(b);
60                if(x == y)
61                printf("In the same gang.\n");
62                else if(op[a]!=0&&find(op[a])==y || op[b]!=0&&find(op[b])==x)
63                printf("In different gangs.\n");
64                else
65                printf("Not sure yet.\n");
66            }
67            else
68            {
69                if(op[a] == 0)
70                op[a] = b;
71                else
72                merge(op[a],b);
73                if(op[b] == 0)
74                op[b] =a;
75                else
76                merge(op[b],a);
77            }
78         }
79     }
80     return 0;
81 }