http://acm.hdu.edu.cn/showproblem.php?pid=1272 

小希的迷宫，第一个做的 并查集的环问题

merge 里面的fa==fb的时候会产生环

#include<iostream>
#include<cstring>
using namespace std;
const int N=1e5+10;
int pre[N],cnt,i,j,flag;
int f(int x)
{
    return x==pre[x]?x:f(pre[x]);
}
void merge(int a,int b)
{
    int fa=f(a),fb=f(b);
    fa==fb?flag=1:pre[fa]=fb;
}
int main()
{
    int a,b;
    while(1)
    {
        memset(pre,0,sizeof(pre));
        flag=0;
        cnt=0;
        while(scanf("%d%d",&a,&b)&&a&&b)
        {
            if(a==-1&&b==-1)
                return 0;
            if(pre[a]==0)
                pre[a]=a;
            if(pre[b]==0)
                pre[b]=b;
            merge(a,b);
        }
        for(i=1;i<N;i++)
            if(pre[i]==i)
                cnt++;
        if(cnt>1||flag)
            printf("No\n");
        else printf("Yes\n"); 
    }
}

View Code