小希的迷宮
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 56590 Accepted Submission(s): 17768
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
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string.h>
using namespace std;
int p[100005];
int findset(int x){
return p[x] == x ? x : p[x] = findset(p[x]);
}
bool cnt[100005];
int main(){
int u, v;
while(1){
int tot = 0, n = 0, num = 0;
for(int i = 1; i <= 100000; ++i){
p[i] = i;
}
memset(cnt, false, sizeof(cnt));
while(scanf("%d %d", &u, &v)){
if(u == 0 && v == 0) break;
if(u == -1 && v == -1) break;
num++;
if(cnt[u] == false){
n++;
cnt[u] = true;
}
if(cnt[v] == false){
n++;
cnt[v] = true;
}
u = findset(u);
v = findset(v);
if(u != v){
tot++;
p[u] = v;
}
}
if(u == -1 && v == -1) break;
if(tot == 0 && n == 0 && num == 0){
printf("Yes\n");
}
else if(n == tot + 1 && tot == num){
printf("Yes\n");
}
else{
printf("No\n");
}
}
}
/*
題意:
給出一些邊,問這些邊是否可以組成一個連通圖且沒有自環。
思路:
并查集維護一下集合,需要注意的是除了判斷自環還要保證圖的連通性,如果沒有點也算Yes。
*/