并查集的题目，才开始做的时候就是想这把他们连接起来,(a,b）顺序从a找b，或从b找a,然后记录路径在判断：可是很多错误，还有在连接两点时部分节点的父亲加点要倒过来很是麻烦。。最后看了别人的结题报告soga..一个人不是属于集合 A，就是属于集合 B。

这样，假设 A、B 两个人不是在同一个 gang 中，A、C 两个人不是在同一个 gang 中，就必定有 B、C 两个人在同一个 gang 中。因此我们可以放心地将 B、C 两个人合并。

也就是说，每次发现 X Y 在不同的集合中，我们都可以将与 X 不在同一集合的与 Y 合并，将与 Y 不在同一集合的与 X 合并。根据并查集的性质，为了在每次合并时找到与其不在一个集合的元素，我们只需要记录他们的一个代表元素即可，于是我们使用 opt[x] 代表一个与 x 不在同一个集合的元素。

#include 
     
      #include 
      
       #include 
       
        using namespace std;const int max_s = 100007;int f[max_s],opt[max_s];int find(int x){    if(f[x]!=x)    f[x]=find(f[x]);    return f[x];}void Union(int x,int y){    int a=find(x);    int b=find(y);    if(a!=b)    f[a]=b;}void init(int n){    int i;    for(i=0;i<=n;i++)    {        f[i]=i;        opt[i]=0;    }}int main(){    //freopen("d.txt","r",stdin);    int t,n,m,x,y;    char op[3];    scanf("%d",&t);    while(t--)    {        scanf("%d%d",&n,&m);        init(n);        while(m--)        {            scanf("%s%d%d",op,&x,&y);            if(op[0]=='D')            {                if(opt[x]==0)                opt[x]=y;                else                Union(opt[x],y);                if(opt[y]==0)                opt[y]=x;                else                Union(opt[y],x);            }            else            {                int a=find(x);                int b=find(y);                if(a==b)                {                    printf("In the same gang.\n");                }                else                {                    if((opt[x]&&find(opt[x])==b)||(opt[y]&&find(opt[y])==x))                    printf("In different gangs.\n");                    else                    printf("Not sure yet.\n");                }            }        }    }    return 0;}