并查集之小希的迷宫

小希的迷宫

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 12513 Accepted Submission(s): 3717
题目链接 http://acm.hdu.edu.cn/showproblem.php?pid=1272

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

心得体会

弄了一个下午还是没有找出错误来真的挺悲剧的案例虽然过了但是还是没有AC 下面那个是发哥的代码再试着写另外一个并查集的题目吧

View Code

  1 #include <iostream>
  2 #include <string>
  3 using namespace  std;
  4 #define  Max 100005
  5 
  6 int p[Max];
  7 bool flag[Max];
  8 int cha(int a)
  9 {
 10     while(p[a]!=-1)
 11     {
 12         a=p[a];
 13     }
 14     return a;
 15 }
 16 
 17 int  bin(int a,int b)
 18 {
 19     a=cha(a);
 20     b=cha(b);
 21     if (a==b)
 22         return 0;
 23     p[a]=b;
 24     return 1;
 25 }
 26 
 27 int main()
 28 {
 29     int a,b;
 30     memset(p,-1,sizeof(p));
 31     memset(flag,false,sizeof(flag));
 32     int t=1;
 33     int m,n,sum=0,i;
 34     while (cin>>a>>b&&a+b!=-2)
 35     {
 36         if (a+b==0)
 37         {
 38             for (i=1;i<Max&&sum<2;i++)
 39             {
 40                 if (flag[i]&&p[i]==0)
 41                 {                   
 42                     sum++;                                     
 43                 }
 44             }
 45             if (sum>1)
 46             {
 47                 t=0;
 48             }
 49             if (t)
 50                 cout<<"Yes"<<endl;  
 51             else    cout<<"No"<<endl;
 52             sum=0;
 53             t=1;
 54             memset(p,-1,sizeof(p));
 55         }
 56         else
 57         {          
 58             flag[a]=flag[b]=true;        
 59             if (!t)
 60             {
 61                 continue;
 62             }
 63             t=bin(a,b);      
 64         }
 65     }
 66     return 0;
 67 }
 68 /*
 69 #include<iostream>
 70 #include<cstdio>
 71 #define MAX 100001
 72 using namespace std;
 73 
 74   int father[MAX];
 75   bool apear[MAX];
 76   int num;
 77   
 78     void Init()
 79     {
 80     memset(father,-1,sizeof(father));
 81     memset(apear,0,sizeof(apear));
 82     num=0;
 83     }
 84     
 85       int Find(int i)
 86       {
 87       while(father[i]!=-1)
 88       i=father[i];
 89       return i;
 90       }
 91       
 92         int  Union(int a,int b)
 93         {
 94         a=Find(a);
 95         b=Find(b);
 96         if(a==b) return 0;
 97         father[a]=b;
 98         return 1;
 99         }
100         
101           int main()
102           {
103           int i,a,b,flag;
104           while(1)
105           {
106           Init();
107           i=flag=1;
108           while(scanf("%d %d",&a,&b)!=EOF)
109           {
110           if(a==0||a==-1) break;
111           if(!flag) continue;
112           apear[a]=1;
113           apear[b]=1;
114           i++;
115           flag=Union(a,b);//????????,???????????;
116           }
117           if(a==-1) break;
118           if(a==0&&i==1)
119           {
120           printf("Yes\n");
121           continue;
122           }
123           int n=0;
124           for(i=1;i<=MAX-1;i++)
125           if(apear[i]&&father[i]==-1)
126           n++;
127           if(n==1&&flag) printf("Yes\n");
128           else printf("No\n");
129           }
130           }
131           */