///////////////////////////////////////////作品名称:并查集应用//作者姓名:满天飞//作品时间:2008-8-15//最后修改:2008-8-15//Q Q 号码:280282813//版权所有,翻版必究/////////////////////////////////////////#include<stdio.h>#define MAX 100010int 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;}

评论