HDU-1272 小希的迷宮 (并查集)

Problem Description

上次Gardon的迷宮城堡小希玩了很久（見Problem B），現在她也想設計一個迷宮讓Gardon來走。但是她設計迷宮的思路不一樣，首先她認為所有的通道都應該是雙向連通的，就是說如果有一個通道連通了房間A和B，那麼既可以通過它從房間A走到房間B，也可以通過它從房間B走到房間A，為了提高難度，小希希望任意兩個房間有且僅有一條路徑可以相通（除非走了回頭路）。小希現在把她的設計圖給你，讓你幫忙判斷她的設計圖是否符合她的設計思路。比如下面的例子，前兩個是符合條件的，但是最後一個卻有兩種方法從5到達8。

Input

輸入包含多組資料，每組資料是一個以0 0結尾的整數對清單，表示了一條通道連接配接的兩個房間的編号。房間的編号至少為1，且不超過100000。每兩組資料之間有一個空行。

整個檔案以兩個-1結尾。

Output

對于輸入的每一組資料，輸出僅包括一行。如果該迷宮符合小希的思路，那麼輸出"Yes"，否則輸出"No"。

Sample Input

6 8 5 3 5 2 6 4

5 6 0 0

8 1 7 3 6 2 8 9 7 5

7 4 7 8 7 6 0 0

3 8 6 8 6 4

5 3 5 6 5 2 0 0

-1 -1

Sample Output

Yes

Yes

No

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int pre[100005];
bool ans, vis[100005];
/*
0.join的時候判斷兩個數是否老大是自己,如果是,那他隻能當小弟
比如: (5,3)(5,2)(4,3)(5,4)
進行第二步時,5有老大,2沒老大(老大是自己),2隻能加入5的老大,如果5的老大(3)加入2的話,
導緻5的老大也是2,在進行最後一步的時候,5的老大是2,4的老大是3,判斷錯誤.
當2加入5的老大,這時候5的老大還是3,4加入5的時候就會發現老大一樣.
1.判斷是否是同一個老大
2.判斷是否隻有一個集合
3.隻有一個點的情況
4.沒有點也輸出Yes
*/
int find(int a){
    int c = a;
    while(a != pre[a])
        a = pre[a];
    pre[c] = a;
    return a;
}
void join(int a, int b){
    int fa = find(a), fb = find(b);
    if(fa == fb && (fa != a || fb != b)) ans = false;
    if( a == fa) pre[fa] = fb;
    else pre[fb] = fa;
}

void one(){
    int a = 0;
    for(int i = 1; i <= 100000; i++){
        if(!vis[i]) continue;
        if(i == pre[i]) a++;
        if(a > 1) {ans = false;return;}
    }
}
int main(){
    while(1){
        int a,b;
        ans = true;
        memset(vis,0,sizeof(vis));
        for(int i = 1; i <= 100000; i++) pre[i] = i;
        while(scanf("%d%d",&a,&b) && a!=0 && b!=0){
            vis[a] = vis[b] = 1;
            if(a == -1 && b ==-1) return 0;
            join(a,b);
        }
        one();
        if(ans) printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}