POJ 1703 Find them, Catch them 种类并查集

Description

Input

Output

Sample Input

1
5 5
A 1 2
D 1 2
A 1 2
D 2 4
A 1 4

Sample Output

Not sure yet.
In different gangs.
In the same gang.

Source

//1136K	704MS
#include<stdio.h>
#define M 100007
int pre[M],rank[M];
char s[1];
int n,m;
void init()
{
    for(int i=1;i<=n;i++)
        {pre[i]=i,rank[i]=0;}
}
int find(int x)
{
    if(x==pre[x])return x;
    int t=pre[x];
    pre[x]=find(pre[x]);
    rank[x]=(rank[x]+rank[t])%2;
    return pre[x];
}
void unio(int a,int b)
{
    int fa=find(a);
    int fb=find(b);
    pre[fa]=fb;
    rank[fa]=(rank[a]+rank[b]+1)%2;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        init();
        int a,b;
        char c;
        for(int i=1;i<=m;i++)
        {
            getchar();
            scanf("%c",&c);
            scanf("%d%d",&a,&b);
            if(c==‘D‘)unio(a,b);
            else
            {
                if(find(a)==find(b))
                {
                    if(rank[a]==rank[b])printf("In the same gang.\n");
                    else printf("In different gangs.\n");
                }
                else printf("Not sure yet.\n");
            }
        }
    }
    return 0;
}