小希的迷宫（并查集，未知点，限定一个老大，判断是否有圈）

- 日理万妓 2022-08-02 01:21 112阅读 0赞

![20150704182231105][]

/*
    这一题是并查集的知识
    常规的并查集是让你找是否连成圈或者连成几个圈或者让你找老大的个数
    这一题是让你在一个老大的情况下（需要判断）判断是否存在圈的问题！
    还有就是这一题没有告诉你有几个点，所以你需要将已知的点标记一下！
    一开始我只想着判断是否有圈去了，其实老大跟圈是没有一点关系的！
    老大多了也可以没有一个圈！
    */
    #include<cstdio>
    #include<iostream>
    #include<cstring>
    const int maxs=100010;
    using namespace std;
    int a[maxs],vis[maxs],flag;
    int Find(int x)
    {
        int r=x;
        while(r!=a[r])
            r=a[r];
        return r;
    }
    void mix(int x,int y)
    {
        int fx=Find(x),fy=Find(y);
        if(fx!=fy)
        {
            a[fy]=fx;
        }
        else
        {
            flag=1;
        }
    }
    int main()
    {
        int b,c,i,num;
        while(scanf("%d%d",&b,&c))
        {
            num=flag=0;
            if(b==-1&&c==-1)
            {
                break;
            }
            if(b==0&&c==0)
            {
                printf("Yes\n");
                continue;
            }
            for(i=1;i<maxs;i++)
            {
                a[i]=i;
                vis[i]=0;
            }
            vis[b]=vis[c]=1;//标记访问的点！
            mix(b,c);
            while(scanf("%d%d",&b,&c),(b+c))
            {
                vis[b]=vis[c]=1;
                mix(b,c);
            }
            for(i=1;i<maxs;i++)
            {
                if(vis[i]&&a[i]==i)
                {
                    num++;
                }
                if(num>1)
                {
                    break;
                }
            }
            if(!flag&&num<=1)
            {
                printf("Yes\n");
            }
            else
            {
                printf("No\n");
            }
        }
    }

[20150704182231105]: /images/20220731/83144411c4764056b657b649dd833bcc.png