#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;

int p[100100];
int rank[100010];
char gank[100010]; // 0 means same as root, 1 different.

int FindSet(int x){
    if(x!=p[x]){
        int tempp = p[x];
        p[x] = FindSet(p[x]);
        if(gank[tempp]!=0)
            gank[x]= 1-gank[x];
    }
    return p[x];
}

// 加入按秩合并就错了?! wtf?!
void Link(int x, int y, char flag){
/*
    if(rank[x]>rank[y]){
        p[y] = x;
        gank[y] = flag;
    }
    else{
        p[x] = y;
        gank[x] = flag;
        if (rank[x]==rank[y])
            rank[y]++;
    }
*/
    p[y] = x;
    gank[y] = flag;
}

void MakeSet(int n){
    int i;
    for(i=1;i<=n;i++)
            p[i]=i;
    memset(rank, 0, n*4);
    memset(gank, 0, n);
}

int main()
{
    int T;
    int n,m,a,b,seta,setb;
    scanf("%d",&T);
    char order;
    while(T--){
        scanf("%d%d",&n,&m);
        getchar();
        MakeSet(n);
        while(m--){
            scanf("%c%d%d", &order, &a, &b);
            getchar();
            seta = FindSet(a);
            setb = FindSet(b);
            if(order=='A'){
                if(n==2){
                    cout<<"In different gangs.\n";
                    continue;
                }
                if(seta == setb){
                    if(gank[a] == gank[b])
                        cout<<"In the same gang.\n";
                    else cout<<"In different gangs.\n";
                }
                else cout<<"Not sure yet.\n";
            }
            else {
                if(seta != setb)
                    Link(seta, setb, gank[a] == gank[b]);
            }
        }
    }
    return 0;
}

• Re:加入按秩合并就WA,不加就可以过,心都碎了,大牛求教啊 (32) qjxkid 2013-05-22 11:10:33