1 /* 2    题目大意：有两个不同的黑帮，开始的时候不清楚每个人是属于哪个的！ 3   执行两个操作 4   A a, b回答a, b两个人是否在同一帮派，或者不确定 5   D a, b表示a, b两个人不在同一个帮派 6  7   思路：利用并查集将相同帮派的人合并到一起！ 8            a ,b 不在同一个城市，那么 a, 和mark[b]就在同一个城市， 9            b 和 mark[a]就在同一个城市！10 */11 #include<iostream>12 #include<cstring>13 #include<cstdio>14 #define M 10000515 using namespace std; 16 int f[M];17 int mark[M];//mark[i]表示 i 与 mark[i]不在同一个黑帮 18 int rank[M];//为不同的集合的父亲节点记录其孩子机节点个数，在合并集合的时候，将19 int n, m;   //rank 值小的集合连接到 rank 值大的集合上去！ 这样在路径压缩的时候省去不少时间 20 21 void init(){22     23    memset(mark, 0, sizeof(int)*(n+1));24    memset(rank, 0, sizeof(int)*(n+1));25    for(int i=1; i<=n; ++i)26       f[i]=i;27 }28 29 int getFather(int x){30    return x==f[x] ? x : f[x]=getFather(f[x]); 31 }32 33 void Union(int a, int b){34    int fa=getFather(a), fb=getFather(b);35    if(fa!=fb){36       if(rank[fa]>rank[fb]){ 37          f[fb]=fa;38          rank[fa]+=rank[fb]+1;39       }40       else{41          f[fa]=fb;42          rank[fb]+=rank[fa]+1;43       }44    }45 } 46 47 int main(){48    int t;49    char cmd[3];50    scanf("%d", &t);51    while(t--){52       scanf("%d%d", &n, &m);53       init();54       while(m--){55          int u, v;56          scanf("%s%d%d", cmd, &u, &v);57          if(cmd[0]==‘A‘){58               int fu=getFather(u), fv=getFather(v);59              if(fu==fv)60                 printf("In the same gang.\n");61              else if(fu==getFather(mark[v]))62                 printf("In different gangs.\n"); 63              else64                 printf("Not sure yet.\n");65          }66          else{67             if(!mark[u] && !mark[v]){68                mark[u]=v;69                mark[v]=u;70             } 71             else if(!mark[u]){72                mark[u]=v;73                Union(u, mark[v]);74             }75             else if(!mark[v]){76                mark[v]=u;77                Union(v, mark[u]);78             }79             else {80                Union(u, mark[v]);81                Union(v, mark[u]);82             }83          }84       }85    } 86    return 0;87 }