【POJ】[1703]Find them, Catch them

并查集的运用
不过这里告诉的是两个人不同组
所以可以仿照食物链那一个
把x+n与y及x与y+n合并
最后只需要检测 x与y 或 x+n与y+n
是否同组就好了

#include<stdio.h>
int par[200200],rank[200200];
int find(int x) {
    if(par[x]==x)
        return x;
    else
        return par[x]=find(par[x]);
}
void unite(int x,int y) {
    x=find(x);
    y=find(y);
    if(x==y)
        return;
    if(rank[x]<rank[y])
        par[x]=y;
    else {
        par[y]=x;
        if(rank[x]==rank[y])
            rank[x]++;
    }
}
int main() {
    int T;
    scanf("%d",&T);
    while(T--) {
        int n,m;
        scanf("%d %d",&n,&m);
        getchar();
        for(int i=1; i<=2*n; i++) {
            par[i]=i;
            rank[i]=0;
        }
        while(m--) {
            char c;
            int x,y;
            scanf("%c %d %d",&c,&x,&y);
            getchar();
            if(c=='D') {
                unite(x,y+n);
                unite(x+n,y);
            } else if(c=='A') {
                if(find(x)==find(y)||find(x+n)==find(y+n))
                    printf("In the same gang.
");
                else if(find(x)==find(y+n)||find(x+n)==find(y))
                    printf("In different gangs.
");
                else
                    printf("Not sure yet.
");
            }
        }
    }
    return 0;
}

题目地址:【POJ】[1703]Find them, Catch them