HDU 1272 小希的迷宫

473 0 0

作者:suvvm

小希的迷宫

上次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

题目解析
　　本题持续输入包含两房间的道路每次输入到0 0开始视为一个迷宫，要求迷宫所有房间连通且任意两个房间之间只有唯一的一条道路，这就要求给出的图是一个无向连通无环图，也就是一棵树，这样我们便可以使用边数加一等于点数与来判断是否是树，维护并查集判断所有点是否连通。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int MAX = 1e5+10;
 4 int f[MAX]; //记录每个房间的父亲
 5 bool flag = false;
 6 bool n[MAX] = {false};  //记录出现过的房间编号
 7 int getF(int x){    //并查集找爹函数
 8     if(x == f[x])
 9         return x;
10     else
11         return f[x] = getF(f[x]);
12 }
13 void unionf(int u, int v){  //合并两点
14     int fu = getF(u);
15     int fv = getF(v);
16     if(fu != fv)    //两者不再一个集合中则将其合并
17         f[fu] = fv;
18 }
19 int main()
20 {
21     int u, v;
22     memset(n, 0, sizeof(n));
23     int edgeCnt = 0;    //记录边数
24     int nodeCnt = 0;    //记录点数
25     int minn = INT_MAX; //记录当前最小房间编号
26     int maxn = 0;   //记录当前最大房间编号
27     for(int i = 0; i < MAX; i++){   //初始化每个结点的父亲为自己
28         f[i] = i;
29     }
30     while(scanf("%d%d", &u, &v) != EOF){    //输入边数据
31         if(u == -1 && v == -1)  //u、v都为-1时结束循环
32             break;
33         if(u == 0 && v == 0){   //u、v都为0时记为一组开始运算
34             if(flag == false){  //如果图中一个房间都没有照样符合题目要求，输出Yes
35                 printf("Yesn");
36                 continue;
37             }
38             int cnt = 0;
39             for(int i = minn; i <= maxn; i++){  //遍历所有房间获取连通块数量
40                 if(n[i] && f[i] == i)
41                     cnt++;
42             }
43             if(cnt > 1){    //若连通块数量大于1则肯定不符合题目要求
44                 printf("Non");
45             }else{
46                 if(edgeCnt + 1 == nodeCnt){ //边数加一为顶点数的图无环
47                     printf("Yesn");
48                 }else{
49                     printf("Non");
50                 }
51             }
52             for(int i = 0; i < MAX; i++){   //初始化每个结点的父亲为自己
53                 f[i] = i;
54             }
55             memset(n, false, sizeof(n));    //初始化所有房间为未出现
56             edgeCnt = 0;    //初始化边数为0
57             nodeCnt = 0;    //初始化点数为0
58             minn = INT_MAX; //最小房间编号初始记为无穷大
59             maxn = 0;   //最大房间编号初始积为0
60             flag = false;
61         }else{
62             edgeCnt++;  //每次输入边数加一
63             maxn = max(max(maxn, u), v);
64             minn = min(min(minn, u), v);
65             //获取当前最大最小房间编号
66             if(!n[u]){  //记录出现过的房间
67                 nodeCnt++;
68                 n[u] = true;
69             }
70             if(!n[v]){
71                 nodeCnt++;
72                 n[v] = true;
73             }
74             unionf(u, v);   //合并道路两端的房间
75         }
76     }
77     return 0;
78 }

内容来源于网络如有侵权请私信删除

标签：算法数据结构

你还没有登录，请先登录或注册！

还没有人评论，欢迎说说您的想法！

HDU 1272 小希的迷宫