HDU 1272 小希的迷宫 (并查集)

小希的迷宫

Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u

Appoint description:

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

判断每次合并的两个是否有相同的父亲，如果是的话答案就是No，另外还要判断一下是否有路，有可能出现有几个森林的情况。另外要注意输入0 0的时候要输出Yes，这是题目的问题，题目并未说清楚。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <string>
 4 #include <queue>
 5 #include <vector>
 6 #include <map>
 7 #include <algorithm>
 8 #include <cstring>
 9 #include <cctype>
10 #include <cstdlib>
11 #include <cmath>
12 #include <ctime>
13 using    namespace    std;
14 
15 const    int    SIZE = 100005;
16 int    FATHER[SIZE],RANK[SIZE];
17 vector<int>    S;
18 
19 void    ini(int);
20 int    find_father(int);
21 bool    unite(int,int);
22 bool    same(int,int);
23 int    main(void)
24 {
25     int    a,b;
26     bool    flag;
27 
28     while(scanf("%d%d",&a,&b) && (a != -1 && b != -1))
29     {
30         if(a == 0 && b == 0)
31         {
32             puts("Yes");
33             continue;
34         }
35         S.clear();
36         S.push_back(a);
37         S.push_back(b);
38         flag = true;
39         ini(SIZE - 2);
40         flag = unite(a,b);
41         while(scanf("%d%d",&a,&b) && (a || b))
42         {
43             flag &= unite(a,b);
44             S.push_back(a);
45             S.push_back(b);
46         }
47         for(int i = 1;i < S.size();i ++)
48             flag &= same(S[0],S[i]);
49         printf("%s
",flag ? "Yes" : "No");
50     }
51 
52     return    0;
53 }
54 
55 void    ini(int n)
56 {
57     for(int i = 1;i <= n;i ++)
58     {
59         FATHER[i] = i;
60         RANK[i] = 0;
61     }
62 }
63 
64 int    find_father(int n)
65 {
66     if(n == FATHER[n])
67         return    n;
68     return    FATHER[n] = find_father(FATHER[n]);
69 }
70 
71 bool    unite(int x,int y)
72 {
73     x = find_father(x);
74     y = find_father(y);
75 
76     if(x == y)
77         return    false;
78     if(RANK[x] < RANK[y])
79         FATHER[x] = y;
80     else
81     {
82         FATHER[y] = x;
83         if(RANK[x] == RANK[y])
84             RANK[x] ++;
85     }
86     return    true;
87 }
88 
89 bool    same(int x,int y)
90 {
91     return    find_father(x) == find_father(y);
92 }