小希的迷宫
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 14388 Accepted Submission(s): 4378
Problem Description
上次Gardon的迷宫城堡小希玩了很久（见Problem B），现在她也想设计一个迷宫让Gardon来走。但是她设计迷宫的思路不一样，首先她认为所有的通道都应该是双向连通的，就是说如果有一个通道连通了房间A和B，那么既可以通过它从房间A走到房间B，也可以通过它从房间B走到房间A，为了提高难度，小希希望任意两个房间有且仅有一条路径可以相通（除非走了回头路）。小希现在把她的设计图给你，让你帮忙判断她的设计图是否符合她的设计思路。比如下面的例子，前两个是符合条件的，但是最后一个却有两种方法从5到达8。
Input
输入包含多组数据，每组数据是一个以0 0结尾的整数对列表，表示了一条通道连接的两个房间的编号。房间的编号至少为1，且不超过100000。每两组数据之间有一个空行。
整个文件以两个-1结尾。
整个文件以两个-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 /* 功能Function Description: HDOJ -1272 2 开发环境Environment: DEV C++ 4.9.9.1 3 技术特点Technique: 4 版本Version: 5 作者Author: 可笑痴狂 6 日期Date: 20120813 7 备注Notes: ----并查集 8 9 */ 10 #include<stdio.h> 11 #include<string.h> 12 13 int set[100001]; 14 int visit[100001]; 15 int flag; 16 17 int find_set(int i) 18 { 19 /* 20 if(i!=set[i]) 21 set[i]=find_set(set[i]); //本题递归式路径压缩会破栈 22 return set[i]; 23 */ 24 int k,t; 25 t=i; 26 while(t!=set[t]) 27 t=set[t]; 28 while(i!=t) //修改路径---压缩 29 { 30 k=set[i]; 31 set[i]=t; 32 i=k; 33 } 34 return i; 35 } 36 37 void merge(int i,int j) 38 { 39 i=find_set(i); 40 j=find_set(j); 41 if(j==i) 42 flag=1; 43 else 44 set[i]=j; 45 } 46 47 int main() 48 { 49 int a,b,i,min,max; 50 while(scanf("%d%d",&a,&b)&&(a!=-1||b!=-1)) 51 { 52 memset(visit,0,sizeof(visit)); 53 visit[a]=visit[b]=1; 54 flag=0; 55 min=a<b?a:b; 56 max=a>b?a:b; 57 if(a==0&&b==0) //测试数据为 0 0 时候注意要输出 Yes 58 { 59 printf("Yes\n"); 60 continue; 61 } 62 else if(a==b) 63 flag=1; 64 for(i=1;i<=100000;++i) 65 set[i]=i; 66 set[a]=b; 67 while(scanf("%d%d",&a,&b)&&(a!=0||b!=0)) 68 { 69 visit[a]=visit[b]=1; 70 if(flag) 71 continue; 72 if(min>(a<b?a:b)) 73 min=a<b?a:b; 74 if(max<(a>b?a:b)) 75 max=a>b?a:b; 76 merge(a,b); 77 } 78 if(flag) 79 printf("No\n"); 80 else //说明不存在回路 81 { 82 for(i=min;i<=max;++i) //判断是否连通 83 { 84 if(visit[i]==0) //没有出现的标号 85 continue; 86 if(set[i]==i) 87 ++flag; 88 } 89 if(flag==1) 90 printf("Yes\n"); 91 else 92 printf("No\n"); 93 } 94 } 95 return 0; 96 }