并查集，带权，水题PKOJ1703

http://poj.org/problem?id=1703

只要两者的关系确定了，就将他们放入同一集合内，而另外增加一个表示关系的数组zt[]来表示该结点与其父亲的关系，0表示是同一类，1表示不同团伙，初始时集合只要自己一个元素，zt[]=0。

#include<stdio.h>//其实只有一个集合，只是在每条边上赋了值罢了,权值 
#include<string.h>
int bin[100002],zt[100002];
int findx(int x)
{
    int r=bin[x];
      if(x==bin[x])
        return bin[x];
     bin[x]=findx(bin[x]);//递归方法查找根结点 
     zt[x]=(zt[x]==zt[r])?0:1;//成立时表示子节点根父亲结点同类，前提是在同一集合里比较 
    return bin[x];
}
void uni(int x,int y,int bx,int by)
{
     bin[bx]=by;//将两个集合合并 
     zt[bx]=(zt[x]==zt[y])?1:0;//因为本来就是分开的两个集合，所以里面的元素比较时就应反向比较 
}
int main()
{
    int n,m,i,x,y,count,t,a,b;
    char s,c[10];
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        gets(c);
        for(i=1;i<=n;i++)
            bin[i] = i,zt[i]=0;//初始化 
        while(m--)
        {
            scanf("%c %d %d",&s,&x,&y);
            gets(c);
            a=findx(x);
            b=findx(y);
            if(s=='D')
                {
                   if(a!=b)uni(x,y,a,b);//没有相同根结点，表示是两个不同的集合，所以应该合并，并对zt值做修改 
                }
           else 
              {
                if(a==b)//在同一个集合里就可以判断 
               {
                 if(zt[x]==zt[y])//相同就是同类 
                        printf("In the same gang.
");  
                    else  
                        printf("In different gangs.
");  
                }  
                else                //不在同一个集合里无法确定  
                    printf("Not sure yet.
");  
               }
        }
    }
    return 0;
}