小希的迷宮

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


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


Input 輸入包含多組數(shù)據(jù)，每組數(shù)據(jù)是一個(gè)以0 0結(jié)尾的整數(shù)對(duì)列表，表示了一條通道連接的兩個(gè)房間的編號(hào)。房間的編號(hào)至少為1，且不超過(guò)100000。每?jī)山M數(shù)據(jù)之間有一個(gè)空行。?
整個(gè)文件以兩個(gè)-1結(jié)尾。

Output 對(duì)于輸入的每一組數(shù)據(jù)，輸出僅包括一行。如果該迷宮符合小希的思路，那么輸出"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 ：：這一題坑死我了，，先是no和yes大小寫(xiě)弄錯(cuò)了，然后是少了等號(hào)，，，，，細(xì)心呀細(xì)心 #include<iostream> #define Size 100001 using namespace std; int father[Size],a[Size]; int find(int x){while(x!=father[x])x=father[x];return x; } void merage(int x,int y){x=find(x);y=find(y);if(x!=y)father[x]=y; } int main() {int i,j,x,y,max;while(cin>>x>>y){if(x==-1&&y==-1)break;for(i=0;i<Size;i++){father[i]=i;a[i]=0;}j=0;max=0;while(x&&y){if(find(x)==find(y))j=1;a[x]=1;a[y]=1;merage(x,y);if(max<x)max=x;if(max<y)max=y;cin>>x>>y;}if(j==1)cout<<"No"<<endl;else {j=0;for(i=0;i<=max;i++)if(a[i]&&father[i]==i)j++;if(j>1)cout<<"No"<<endl;else cout<<"Yes"<<endl;}} }

總結(jié)

以上是生活随笔為你收集整理的小希的迷宫的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。