小希的迷宮

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 35517 Accepted Submission(s): 10854


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

 

 

【題意】

給你一個圖的描述，要求圖聯通，且圖不成環；

用並查集可以簡單的解決。 注意邊界條件，輸入一條邊 例如 1 1 0 0 或者一條邊也不輸入 0 0 ，也要輸出Yes。

【代碼】

 

#include 
#include 
#include 
#include 
using namespace std;
const int maxp=100005;
struct Parent{
	int value,rank;
}parent[maxp];
void MakeSet(){ //初始化
	for(int i=1;iparent[yroot].rank) // 按秩合並
		parent[yroot].value=xroot;
	else if(parent[xroot].rankst;
	MakeSet();
	int sign=0;int cnt=0; //代碼寫的冗雜，出現很多細節問題要處理
	while(scanf(%d%d,&a,&b)!=EOF){
		if(a==-1&&b==-1) break;
		if(a==0&&b==0){
			if(cnt==1||cnt==0){
				printf(Yes
); 
				cnt=0;st.clear();MakeSet();sign=0;
				continue;
			}
			if(sign){
				printf(No
);cnt=0;st.clear();MakeSet();sign=0;;continue;
			}
			int ans=0;			
			for(set::iterator it=st.begin();it!=st.end();++it){ //用set來儲存輸入的數據
				if(parent[*it].value==*it){
					ans++;
				}
			}
			cnt=0;st.clear();MakeSet();sign=0;
			if(ans==1){
				printf(Yes
);
			}
			else
				printf(No
);
			}
			
		else{
			int tmp=Union(a,b);
			st.insert(a);
			st.insert(b);
			if(!tmp){
				sign=1;
			}
			cnt++;
		}
	}
	return 0;
}