http://poj.org/problem?id=1703
题目大意
警察抓了个罪犯,这些罪犯只可能属于两个团伙中的一个,
现在给出M个语句
(D a b)表示a和b不在同一团伙
(A a b)表示查询a与b的关系

渣速度。。。。

#include<stdio.h>
int f[100010],rela[100010];
int Find(int x){
    if(x!=f[x]){
        int tmp=f[x];
        f[x]=Find(f[x]);
        rela[x]=(rela[x]==rela[tmp])?0:1;//额外增加的关系
    }
    return f[x];
}
int Union(int x,int y){
    int px=Find(x);
    int py=Find(y);
    if(px!=py){
        f[px]=py;
        rela[px]=(rela[x]==rela[y])?1:0;
    }
}
int main(){
    int T,N,M,i,a,b;
    char cmd;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&N,&M);
        for(i=0;i<=N;i++){
            f[i]=i;
            rela[i]=0;
        }
        while(M--){
            scanf("\n%c%d%d",&cmd,&a,&b);
            if(cmd=='D'){
                Union(a,b);
            }
            if(cmd=='A'){
                int px=Find(a);
                int py=Find(b);
                if(px!=py){
                    printf("Not sure yet.\n");continue;
                }
                if(rela[a]==rela[b]){
                    printf("In the same gang.\n");continue;
                }
                else {
                    printf("In different gangs.\n");continue;
                }
            }
        }
    }
    return 0;
}
原创文章采用 CC BY-NC-SA 4.0协议 进行许可,转载请著名转自: POJ 1703 Find them, Catch them 并查集