/////////////////////////////////////////
//作品名称:并查集应用
//作者姓名:满天飞
//作品时间:2008-8-15
//最后修改:2008-8-15
//Q Q 号码:280282813
//版权所有,翻版必究
/////////////////////////////////////////


#include<stdio.h>
#define MAX 100010
int ary[MAX];
int opt[MAX];
void Init(int n)
{
    int i;
    for(i = 0; i <= n+10; ++i)
    {
        ary[i] = -1;
        opt[i] = -1;
    }
}

int Find(int index)
{
    if(ary[index] < 0)
        return index;
    return ary[index] = Find(ary[index]);
}
int Union(int first, int second)
{
    int i, j;
    if(second == -1)
        return first;

    i = Find(first);
    j = Find(second);
    if(i == j)
        return i;
    if(ary[i] < ary[j])
    {
        ary[i] += ary[j];
        ary[j] = i;
        return i;
    }
    else
    {
        ary[j] += ary[i];
        ary[i] = j;
        return j;
    }
    return -1;
}

void UnionDiff(int first, int second)
{
    int r1, r2, d1, d2;
    r1 = Find(first);
    r2 = Find(second);
    if(r1 == r2)
        return;
    //合并两次
    d1 = Union(r1, opt[r2]);
    d2 = Union(r2, opt[r1]);
    opt[d1] = d2;
    opt[d2] = d1;
}

int main(int argv, char* argc[])
{
    int cases, num, msg, i, f, s, r1, r2;
    char ch;
    scanf("%d", &cases);
    while(cases--){
        scanf("%d%d", &num, &msg);
        Init(num);
        for(i = 0; i < msg; ++i){
            getchar();
            scanf("%c %d %d", &ch, &f, &s);
            if(ch == 'D')
                UnionDiff(f, s);
            else{
                r1 = Find(f);
                r2 = Find(s);
                if(r1 == r2)
                    printf("In the same gang.\n");
                else if(r1 == opt[r2])
                    printf("In different gangs.\n");
                else printf("Not sure yet.\n");
            }
        }
    }
    return 0;
}

评论