HDU-1272小希的迷宮（并查集的運用）

小希的迷宮

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)

題目連結http://acm.hdu.edu.cn/showproblem.php?pid=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

題目的本質就是讓你判斷是否為一棵樹，然後我們可以用并查集将所有節點的父節點并到根節點，下一次判斷時，如果兩個點的父節點都是同一個，則一定是有子節點兩兩相連了。

int fa=find(u),fb=find(v);
if (fa!=fb) {
	father[fa]=fb;
} 
else {
	mark=1;  //标記
}
           

然後我們很快就可以寫出代碼了：

#include <cstdio>
#include <cstring>
#define mac 100010
using namespace std;
int father[100050];
void init()
{
    for (int i=1; i<=mac; i++) father[i]=i;
}
int find(int x)
{
    return x==father[x]?x:find(father[x]);
}
int main()
{
    int u,v,mark=0;
    init();
    while (scanf ("%d%d",&u,&v)){
        if(u==-1 && v==-1) break;
        if (!u && !v){
            if (!mark) printf ("Yes\n");
            else printf ("No\n");
            init();
            mark=0;
        }
        else {
            int fa=find(u),fb=find(v);
            if (fa!=fb){
                father[fa]=fb;
            }
            else {
                mark=1;
            }
        }
    }
    return 0;
}
           

交一發，果斷WA了，想一想為什麼，題目沒有說明輸入的資料保證隻是一棵樹，是以要判斷多棵樹存在的情況。然後就改改

#include <cstdio>
#include <cstring>
#define mac 100010
using namespace std;
int father[100050],vis[100050];
void init()
{
    for (int i=1; i<=mac; i++) father[i]=i;
    memset(vis,0,sizeof(vis));
}
int find(int x)
{
    return x==father[x]?x:find(father[x]);
}
int main()
{
    int maxx=-2,u,v,mark=0,cnt=0;
    init();
    while (scanf ("%d%d",&u,&v)){
        if(u==-1 && v==-1) break;
        maxx=(maxx>u)?maxx:u;
        maxx=(maxx>v)?maxx:v;
        vis[u]=vis[v]=1;
        if (!u && !v){
            if (!mark) {
            	for (int i=1; i<=maxx; i++){     //是否有多個根節點
            		if (vis[i] && father[i]==i) cnt++; 
				}
				if (cnt>1) printf ("No\n");
            	else printf ("Yes\n");
			}
            else printf ("No\n");
            init();
            mark=0;cnt=0;
        }
        else {
            int fa=find(u),fb=find(v);
            if (fa!=fb){
                father[fa]=fb;
            }
            else {
                mark=1;
            }
        }
    }
    return 0;
}