poj 1703

rank 用于记录祖先的等级
opp 用于记录敌人。。
 1 #include <iostream>
 2 #include<cstdio>
 3 using namespace std;
 4 int f[100005];
 5 int rank[100005],opp[100005];
 6 char str[3];
 7 void init(int n){
 8     for(int i=1;i<=n;i++){
 9         f[i] = i;
10         rank[i]=opp[i]=0;
11     }
12 }
13 
14 int find(int x){
15     if(x!=f[x])
16         f[x] = find(f[x]);
17     return f[x];
18 }
19 
20 void unin(int a,int b){
21     int fa = find(a);
22     int fb = find(b);
23     if(fa==fb)
24         return ;
25     if(rank[fa]>rank[fb])
26         f[fb] = fa;
27     else{
28         f[fa] = f[fb];
29         if(rank[fa]==rank[fb])
30             rank[fb]++;
31     }
32 }
33 int main()
34 {
35     int t;
36     scanf("%d",&t);
37     while(t--){
38         int n,m;
39         scanf("%d%d",&n,&m);
40         init(n);
41         int a,b;
42         for(int i=1;i<=m;i++){
43             scanf("%s%d%d",str,&a,&b);
44             int fa = find(a);
45             int fb = find(b);
46             if(str[0]=='A'){
47                 if(fa==fb){
48                     printf("In the same gang.
");
49                 }
50                 else if(fa==find(opp[fb]))//如果fa！=fb  但是fa和b的敌人的祖先相同，那么a，b。不同族群
51                     printf("In different gangs.
");
52                 else
53                     printf("Not sure yet.
");
54             }
55             else{
56                 if(opp[a]==0)
57                     opp[a] = fb;
58                 if(opp[b]==0)
59                     opp[b]=fa;
60                 unin(a,opp[fb]);//合并
61                 unin(b,opp[fa]);
62             }
63         }
64     }
65     return 0;
66 }