?

小希的迷宮

Time Limit: 2000/1000 MS (Java/Others)????Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 14112????Accepted Submission(s): 4284

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

?

Author Gardon

?

Source HDU 2006-4 Programming Contest

?

Recommend lxj

?

?

?

?

?

?

[轉]http://hi.baidu.com/faithyzy/item/0742e5495f9f63a8df2a9fea

題目大意：小希要做一個迷宮，迷宮中任意兩個房間有且僅有一條路徑可以相通（除非走了回頭路）。

這樣，就需要用到并查集了（赤裸裸的），對于輸入的兩個頂點，判斷是否在同一個集合內，是的話，就是存在多條通路了，而對于一個迷宮，所有的點最后必須在同一個集合內（這一個問題剛開始沒有考慮到，貢獻了兩次WA），處理好這兩個問題，就可以了

有一個比較特殊的情況，就是輸入的那一組數據只有兩個0，必須輸出 Yes

網上有很多人寫了這個題目的解題報告，但大家都是用一個數組來記錄是否用過，然后對用過的點進行尋根，最后看一下是不是所有有用過的點都是同一個根，我覺得沒有必要，只要記錄點是否用過，最后，連接的邊和用到的點的差是1就可以了，也就是說連接n個點，只要n-1條邊，so~~

code:

1 #include <stdio.h> 2 #include <string.h> 3 int r[100001]; //記錄父節點 4 bool used[100001]; //是否使用過 5 6 int find(int x) 7 { 8 while (r[x]!=x) 9 x=r[x]; 10 return x; 11 } 12 13 int bing(int x,int y) 14 { 15 x=find(x); 16 y=find(y); 17 if (x==y) 18 return 0; 19 r[y]=x; 20 return 1; 21 } 22 23 int main () 24 { 25 int n,m,flag,i,t; 26 while (scanf("%d %d",&n,&m)!=EOF) 27 { 28 if (n==-1 && m==-1) 29 return 0; 30 if (n==0 && m==0) //當一開始就輸入0 0的話，要輸出Yes 31 { 32 printf ("Yes\n"); 33 continue; 34 } 35 memset(used,0,sizeof(used)); 36 for (i=0;i<100001;i++) 37 r[i]=i; 38 bing(n,m); 39 used[n]=1; 40 used[m]=1; 41 t=1; //t代表當前點數和邊數的差值 剛開始時是2-1=1 42 flag=1; //flag表示當前所有點的根是否唯一 43 while (scanf("%d %d",&n,&m)!=EOF) 44 { 45 if (n==0 && m==0) 46 break; 47 if (used[n]==0) 48 { 49 t++; //新加入了一個點，故t++ 50 used[n]=1; //標記點已經被記錄過 51 } 52 if (used[m]==0) 53 { 54 t++; 55 used[m]=1; 56 } 57 if (bing(n,m)==0) 58 flag=0; //若n和m的根節點相同，并且他們又彼此連通，則說明構成環，故不符合 59 else 60 t--; //若n和m的根節點不相同，則將他們合并，并且邊數+1，相當于t-1 61 } 62 if (flag && t==1) //若圖中沒有環，而且點數與邊數相差1，則說明該圖是符合的！ 63 printf ("Yes\n"); 64 else 65 printf ("No\n"); 66 } 67 return 0; 68 }

?

轉載于:https://www.cnblogs.com/XBWer/archive/2012/08/07/2626962.html

總結

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

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