POJ 1703 Find them, Catch them

 1 //#define LOCAL
 2 #include <iostream>
 3 #include <cstdio>
 4 #include <cstring>
 5 using namespace std;
 6 
 7 const int maxn = 100000 + 10;
 8 int p[maxn], r[maxn];
 9 
10 int Find(int a)
11 {
12     if(p[a] == a)    return a;
13     int temp = p[a];
14     p[a] = Find(p[a]);
15     r[a] = (r[a] ^ r[temp]);
16     return p[a];
17 }
18 
19 int main(void)
20 {
21     #ifdef LOCAL
22         freopen("1703in.txt", "r", stdin);
23     #endif
24 
25     int T;
26     scanf("%d", &T);
27     while(T--)
28     {
29         int n, m, x, y;
30         char cmd[10];
31         scanf("%d %d", &n, &m);
32         for(int i = 0; i <= n; ++i)    p[i] = i;
33         memset(r, 0, sizeof(r));
34         for(int i = 0; i < m; ++i)
35         {
36             scanf("%s %d %d", cmd, &x, &y);
37             int px = Find(x);
38             int py = Find(y);
39             if(cmd[0] == ‘A‘)
40             {
41                 if(px != py)
42                     printf("Not sure yet.\n");
43                 else
44                 {
45                     if((r[x] + r[y]) % 2)
46                         printf("In different gangs.\n");
47                     else
48                         printf("In the same gang.\n");
49                 }
50             }
51             else
52             {
53                 p[px] = py;
54                 r[px] = 1 - (r[x] ^ r[y]);
55             }
56         }
57     }
58     return 0;
59 }