HDU 1272 小希的迷宫（并查集）

题目链接：http://acm.split.hdu.edu.cn/showproblem.php?pid=1272

题目大意：上次Gardon的迷宫城堡小希玩了很久（见Problem B），现在她也想设计一个迷宫让Gardon来走。但是她设计迷宫的思路不一样，首先她认为所有的通道都应该是双向连通的，就是说如果有一个通道连通了房间A和B，那么既可以通过它从房间A走到房间B，也可以通过它从房间B走到房间A，为了提高难度，小希希望任意两个房间有且仅有一条路径可以相通（除非走了回头路）。小希现在把她的设计图给你，让你帮忙判断她的设计图是否符合她的设计思路。比如下面的例子，前两个是符合条件的，但是最后一个却有两种方法从5到达8。

解题思路：常规并查集，注意几点：

　　　　　①当a 和b有相同头节点，也就是a,b已经属于同一个并查集，再连接a b则会成环。

　　　　　②当输入为0 0是即迷宫为空，答案为Yes.

　　　　　③不能有多片森林，所有点只能在一个并查集中。

代码：

 1 #include<cstdio>
 2 #include<cmath>
 3 #include<cctype>
 4 #include<cstring>
 5 #include<iostream>
 6 #include<algorithm>
 7 #include<vector>
 8 #include<queue>
 9 #include<set>
10 #include<map>
11 #include<stack>
12 #include<string>
13 #define LC(a) (a<<1)
14 #define RC(a) (a<<1|1)
15 #define MID(a,b) ((a+b)>>1)
16 using namespace std;
17 typedef long long LL;
18 const int INF=0x3f3f3f3f;
19 const int N=1e5+5;
20 
21 int root[N],rec[N];//rec[i]=1表示数字i出现过 
22 
23 int find(int x){
24     return root[x]==x?x:root[x]=find(root[x]);
25 }
26 
27 int main(){
28     int a,b,flag,cas=0;
29     while(1){
30         for(int i=1;i<=N;i++)
31             root[i]=i;
32         memset(rec,0,sizeof(rec));
33         flag=1;
34         while(~scanf("%d%d",&a,&b)&&(a||b)){
35             if(a==-1&&b==-1)
36                 return 0;
37             rec[a]=rec[b]=1;
38             //判断是否成环 
39             if(find(a)==find(b))
40                 flag=0;
41             root[find(a)]=find(b);
42         }
43         int sum=0;
44         //判断只有一个并查集 
45         for(int i=1;i<=N;i++){
46             if(root[i]==i&&rec[i])
47                 sum++;
48         }
49         if(sum>1||!flag)
50             puts("No");
51         else
52             puts("Yes");
53     }
54     return 0;
55 }