poj1703 并查集

 输入是2个不在一起的人，可以用一个数组来保存和他矛盾的人。这样find的时候就find（hash[]);就可以；

#include<stdio.h>
#include<string.h>
int pa[100020],h[100020],n;
void init()
{
    for(int i=0;i<=n;i++)
    {
        pa[i]=i;
        h[i]=0;
    }
}
int find(int x)
{
    if(x!=pa[x])
        pa[x]=find(pa[x]);
    return pa[x];
}
int main()
{
    int i,j,t,m;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        getchar();
        init();
        char s;
        int a,b;
        for(i=0;i<m;i++)
        {
            scanf("%c %d %d",&s,&a,&b);
            getchar();
            if(s=='D')
            {
                if(!h[a])
                    h[a]=b;
                else
                {
                    int l1,l2;
                    l1=find(h[a]);
                    l2=find(b);
                    pa[l1]=l2;
                }
                if(!h[b])
                    h[b]=a;
                else
                {
                    int l1,l2;
                    l1=find(h[b]);
                    l2=find(a);
                    pa[l1]=l2;
                }

            }
            else
            {
                /*if(n==2)
                {
                    if(a!=b)
                    printf("In different gangs.
");
                    else
                        printf("In the same gang.
");
                    continue;
                }*/
                int l1=find(a);
                int l2=find(b);
                int l3=find(h[b]);
                if(h[l1]==0||h[l2]==0)
                {
                    printf("Not sure yet.
");
                    continue;
                }
                if(l1==l2)
                    printf("In the same gang.
");
                else if(l1==l3)
                {
                    printf("In different gangs.
");
                }
                else
                    printf("Not sure yet.
");
                
            }
        }
    }
}