小希的迷宫

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)

Total Submission(s): 18853 Accepted Submission(s): 5732

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

简单并查集，双向连通图

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 #include
          
             6 using namespace std;  7   8 int parent[100001];  9 int n,m; 10  11 void Ufset() 12 { 13     int i; 14     for(i=1;i<=100000;i++) 15     { 16         parent[i]=-1; 17     } 18 } 19  20 int Find(int x) 21 { 22     int s; 23     for(s=x;parent[s]>0;s=parent[s]){} 24     while(s!=x) 25     { 26         int temp=parent[x]; 27         parent[x]=s; 28         x=temp; 29     } 30     return s; 31 } 32  33 void Union(int R1,int R2) 34 { 35     int r1=Find(R1),r2=Find(R2); 36     int temp=parent[r1]+parent[r2]; 37     if(parent[r1]>parent[r2]) 38     { 39         parent[r1]=r2; 40         parent[r2]=temp; 41     } 42     else 43     { 44         parent[r2]=r1; 45         parent[r1]=temp; 46     } 47 } 48  49 int main() 50 { 51     int u,v; 52     while(scanf("%d%d",&u,&v)!=EOF) 53     { 54         Ufset(); 55         int flag=0; 56         if(u==-1&&v==-1)break; 57         if(u==0&&v==0) 58         { 59             printf("Yes\n");continue; 60         } 61         if(Find(u)!=Find(v)) 62         { 63             Union(u,v); 64         } 65         else 66         { 67             flag=-1; 68         } 69         while(scanf("%d%d",&u,&v)!=EOF) 70         { 71             if(!u&&!v)break; 72             if(Find(u)!=Find(v)&&flag!=-1) 73             { 74                 Union(u,v); 75             } 76             else 77             { 78                 flag=-1; 79             } 80         } 81         if(flag==-1) 82         { 83             printf("No\n"); 84         } 85         else 86         { 87             int i; 88             int tmp=0; 89             for(i=1;i<=100000;i++) 90             { 91                 if(parent[i]<-1) 92                     tmp++; 93             } 94             if(tmp>=2) 95             { 96                 printf("No\n"); 97             } 98             else 99                 printf("Yes\n");100         }101     }102     return 0;103 }