poj1703 Find them, Catch them

并查集。
这题错了不少次才过的。
分析见代码。
 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 using namespace std;
 5 const int maxn = 1e5 + 10;
 6 const char str1[] = "Not sure yet.";
 7 const char str2[] = "In different gangs.";
 8 const char str3[] = "In the same gang.";
 9 int fa[maxn], belong[maxn], nex[maxn];
10 int n, m, u, v, k;
11 char op;
12 
13 int father(int u){
14     //WHAT WOULD CAUSE AN INFINITE LOOP
15     if(fa[u] == -1) return u;
16     int tem = father(fa[u]);
17     belong[u] = belong[tem];
18     fa[u] = tem;
19     return tem;
20 }
21 
22 void solve(){
23     if(op == 'D'){
24         if(belong[u] == -1 && belong[v] == -1){
25             //this is the simplest case
26             belong[u] = k++;
27             belong[v] = k++;
28             nex[u] = v;
29             nex[v] = u;
30             return;
31         }
32         if(belong[u] != -1 && belong[v] == -1){
33             //notice that v is never mentioned, but u is already processed
34             //since is u is vistied, u got its partner
35             int fu = father(u), fu1 = father(nex[u]);
36             //draw a line from v to u1
37             fa[v] = fu1;
38             nex[v] = fu;
39             belong[v] = belong[fu1];
40             return;
41             //match a virtue partner for node u
42         }
43         if(belong[u] == -1 && belong[v] != -1){
44             int fv = father(v), fv1 = father(nex[v]);
45             fa[u] = fv1;
46             nex[u] = fv;
47             belong[u] = belong[fv1];
48             return;
49         }
50         if(belong[u] != -1 && belong[v] != -1){
51             //notice that both u and v is already visited
52             int fu = father(u), fu1 = father(nex[u]);
53             int fv = father(v), fv1 = father(nex[v]);
54             int bu = belong[fu] >> 1;
55             int bv = belong[fv] >> 1;
56             if(bu > bv){
57                 // v is relatively primitive
58                 fa[fu] = fv1;
59                 fa[fu1] = fv;
60                 return;
61             }
62             if(bu < bv){
63                 fa[fv] = fu1;
64                 fa[fv1] = fu;
65                 return;
66             }
67         }
68     }
69     if(op == 'A'){
70         int fu = father(u);
71         int fv = father(v);
72         if(belong[fu] == -1 || belong[fv] == -1) puts(str1);
73         else if(belong[fu] == belong[fv]) puts(str3);
74         else if(belong[fu] == (1 ^ belong[fv])) puts(str2);
75         else puts(str1);
76     }
77 }
78 
79 int main(){
80     freopen("in.txt", "r", stdin);
81     int T;
82     scanf("%d", &T);
83     while(T--){
84         scanf("%d%d", &n, &m);
85         memset(belong, -1, sizeof belong);
86         memset(fa, -1, sizeof fa);
87         k = 0;
88         for(int i = 0; i < m; i++){
89             scanf(" %c%d%d", &op, &u, &v);
90             solve();
91         }
92     }
93 }
View Code