小希的迷宮

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

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


Input 輸入包含多組數據，每組數據是一個以0 0結尾的整數對列表，表示了一條通道連接的兩個房間的編號。房間的編號至少為1，且不超過100000。每兩組數據之間有一個空行。?
整個文件以兩個-1結尾。

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

Sample Input 6 8 5 3 5 2 6 4 5 6 0 08 1 7 3 6 2 8 9 7 5 7 4 7 8 7 6 0 03 8 6 8 6 4 5 3 5 6 5 2 0 0-1 -1
Sample Output Yes Yes No 這道并查集的題目與其他題目相比，有幾個要注意地方：1.房間編號并不是1—n，有些數字并沒有出現，所以要用一個數組標記數字是否出現；2.如果查找到輸入的兩個數字的根節點相同，說明它們已經連通了，再加一條邊就有多條相通的路徑，用FLAG記錄是否有多條相通路徑；3.要判斷所有房間是不是屬于同一個集合。 //flag[i]數組標記i是否出現，FLAG標記是否有環，sum記錄集合的個數 #include<stdio.h> const int N = 100005; int flag[N], father[N]; void Init() {for(int i = 0; i <= 100000; i++)flag[i] = 0, father[i] = i; } int Find(int x) {if(x != father[x])father[x] = Find(father[x]);return father[x]; } void Merge(int a, int b) {int p = Find(a);int q = Find(b);if(p > q)father[p] = q;elsefather[q] = p; } int main() {int a, b;while(~scanf("%d%d",&a,&b)){if(a == -1 && b == -1)break;Init();int FLAG = 0;while(1){if(a == 0 && b == 0)break;if(Find(a) == Find(b))FLAG = 1;Merge(a,b);flag[a] = 1, flag[b] = 1;scanf("%d%d",&a,&b);}if(FLAG == 1)printf("No\n");else{int sum = 0;for(int i = 0; i <= 100000; i++)if(flag[i] && father[i] == i)sum++;if(sum > 1)printf("No\n");elseprintf("Yes\n");}}return 0; }

總結

以上是生活随笔為你收集整理的hdu 1272 小希的迷宫 （并查集）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。