小希的迷宫

http://acm.hdu.edu.cn/showproblem.php?pid=1272

View Code

 1 #include <stdio.h>
 2 int father[100001],k[100001];
 3 int flag ;
 4 int find(int x)
 5 {
 6     while(x!=father[x])
 7     x = father[x] ;
 8     return x ;
 9 }
10 void merge(int x,int y)
11 {
12     int fx , fy ;
13     fx = find(x) ;
14     fy = find(y) ;
15     if(fx!=fy)
16     father[fx] = fy;
17     else flag = 0 ;//同父节点，成环
18 }
19 int main()
20 {
21     int i, a, b ;
22     while(scanf("%d%d",&a,&b),a!=-1,b!=-1)
23     {
24         if(a==0&&b==0)
25         {
26             printf("Yes\n");
27             continue;
28         }
29         for(i=1; i<=100001; i++)
30         {
31             father[i] = i;
32             k[i] = 0 ;//注意初始化
33         }
34         flag = 1 ;
35         k[a] = k[b] = 1 ;
36         merge(a, b) ;
37         while(scanf("%d%d",&a,&b),a!=0,b!=0)
38         {
39             merge(a, b) ;
40             k[a] = k[b] = 1 ;
41         }
42         int num = 0;
43         for(i = 0 ; i < 100001 ; i++)
44         {
45             if(father[i]==i&&k[i])//判断根节点的数目
46             num++;
47             if(num>1)
48             flag = 0;
49         }
50         if(flag)
51         printf("Yes\n");
52         else
53         printf("No\n");
54     }
55     return 0;
56 }

总结：题目意思是找到判断是不是连通无环的图，首先想到的就是并查集。

1判断成环的时候，只要判断输入边的两个点。有一个共同的父节点，那么这两个点就成环。

2判断连通的时候，只要判断根节点数为1即可。

注意：当输入的这组数据只有 0 0 时，依然是满足条件的，即应输出 "Yes"。