NWU CCCC 1017（HDU 1272改编 并查集判断图是否存在环）

Evio与观察小白鼠

Time Limit : 3000/1000ms (Java/Other)   Memory Limit : 65535/32768K (Java/Other)

Total Submission(s) : 13   Accepted Submission(s) : 3

Font: Times New Roman | Verdana | Georgia

Font Size: ← →

Problem Description

Evio非常喜欢生物，Evio现在想观察小白鼠的记忆能力。Evio想设计一个任意两个房间只有一条路径的地图。这个地图有m条双向通道，这条通道连接房间A和房间B，由于地图过于复杂，Evio想请你帮忙判断这个地图是否满足要求。

Input

每组数据第一行有一个正整数m(2<=n<=1000)。
接下来n行有两个正整数A B（1<=A,B<=10000），表示房间A和房间B之间有条双向通道。

Output

输出一行，表示地图是否满足要求，满足要求时输出”Yes”，否则输出”No”。

Sample Input

2
1 2
2 3
2
1 2
3 4

Sample Output

Yes
No

思路：为了防止 （1，2）（3，4）这种情况，需要判断集合的个数，当且仅当只有一个集合的时候才满足题意。

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

int F[10005];
int visit[10005];

int get_far(int x){
    return F[x] == x ? x : F[x] = get_far(F[x]);
}
void Union(int x,int y){
    int a = get_far(F[x]),b = get_far(F[y]);
    if(a != b)
        F[a] = b;
}

int main()
{
    int n;
    while(cin>>n){
        memset(visit,0,sizeof(visit));
        for(int i = 0;i <= 20000;i ++)   F[i] = i;

        int a,b;
        int flag = 0;
        int maxn=-1;
        int minn=99999999;

        for(int i = 1;i <= n;i ++){
            scanf("%d%d",&a,&b);
            maxn = max(maxn,max(a,b));
            minn = min(minn,min(a,b));
            if(get_far(F[a]) != get_far(F[b]))
                Union(a,b);
            else
                flag = 1;
            visit[a] = visit[b] = 1;
        }

        int ans = 0;
        if(flag)    cout<<"No"<<endl;
        else{
            for(int i = minn;i <= maxn;i ++){
               int x = get_far(i);
               if(x == i && visit[i])       //得到了集合的个数
                    ans++;
            }
            if(ans == 1)    cout<<"Yes"<<endl;
            else//集合个数不为 1 个的时候，必然不满足题意。
                cout<<"No"<<endl;
        }
    }
    return 0;
}