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

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <queue>
 5 #include <cmath>
 6 using namespace std;
 7 
 8 int N,M;
 9 int f[2*100000+10];
10 
11 void init()
12 {
13     for(int i=1;i<=2*N;i++)
14     {
15         f[i] = i;
16     }
17 }
18 
19 int find( int x)
20 {
21     return f[x] == x? x: f[x] = find(f[x]);
22 }
23 
24 int a,b;
25 char c;
26 void readin()
27 {
28     getchar();
29     c = getchar();scanf("%d%d",&a,&b);
30 }
31 bool same ( int a, int b)
32 {
33     int fa  = find(a) , fb =find( b);
34     if( fa == fb)return true;
35     return false;
36 }
37 
38 void uni(int a,int b)
39 {
40     int fa = find(a), fb = find(b);
41     if( fa != fb)
42         f[fb] = fa;
43 }
44 
45 int main()
46 {
47     int T;
48     cin>>T;
49     while(T--)
50     {
51         cin>>N>>M;
52         init();
53         for(int i=0;i<M;i++)
54         {
55             readin();
56 
57             if(c == ‘A‘)
58             {
59                 if (same ( a, b ) || same( a+N , b+N))
60                     cout<<"In the same gang."<<endl;
61                 else if( same( a, b+N) || same(b, a+N))
62                     cout<<"In different gangs."<<endl;
63                 else
64                     cout<<"Not sure yet."<<endl;
65             }
66             if( c== ‘D‘)
67             {
68                 uni ( a, b+N  );
69                 uni ( b, a+N);
70             }
71 
72         }
73     }
74 
75 
76     return 0;
77 }