小希的迷宫 并查集
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include<algorithm>
#include<iostream>
#include<queue>
using namespace std;
int a[100005];
void s()
{
for(int i=0;i<100000;i++)
{
a[i] = i;
}
}
int find(int x)
{
if (a[x] == x)
{
return x;
}
else
{
return a[x]=find(a[x]);
}
}
int main()
{
int n1, n2;
while (cin >> n1 >> n2)
{
if (n1 == -1)
{
break;
}
int maxnum = 0;
s();
bool judge = true;
while (n1 !=0 && n2 != 0)
{
n1 > n2 ? maxnum = n1 : maxnum = n2;
if (find(n1) == find(n2))
{
judge = false;
}
else
{
a[find(n1)] = a[find(n2)];
}
cin >> n1 >> n2;
}
//判断是否所有出现过的房间都相通
int temp=0;
for (int i = 0; i <= maxnum; i++)
{
if (a[i] != i)
{
if (temp == 0)
{
temp = find(a[i]);
}
else
{
if (temp != find(a[i]))
{
judge = false;
}
}
}
}
if(judge)
{
cout << "Yes\n";
}
else
{
cout << "No\n";
}
}
return 0;
} Contrib Contrib/a11y/accessibility-menu.js
<dl><dd>
整个文件以两个-1结尾。
</dd> Output <dd> 对于输入的每一组数据，输出仅包括一行。如果该迷宫符合小希的思路，那么输出"Yes"，否则输出"No"。
</dd> Sample Input <dd> </dd></dl>
上次Gardon的迷宫城堡小希玩了很久（见Problem B），现在她也想设计一个迷宫让Gardon来走。但是她设计迷宫的思路不一样，首先她认为所有的通道都应该是双向连通的，就是说如果有一个通道连通了房间A和B，那么既可以通过它从房间A走到房间B，也可以通过它从房间B走到房间A，为了提高难度，小希希望任意两个房间有且仅有一条路径可以相通（除非走了回头路）。小希现在把她的设计图给你，让你帮忙判断她的设计图是否符合她的设计思路。比如下面的例子，前两个是符合条件的，但是最后一个却有两种方法从5到达8。
</dd> Input <dd> 输入包含多组数据，每组数据是一个以0 0结尾的整数对列表，表示了一条通道连接的两个房间的编号。房间的编号至少为1，且不超过100000。每两组数据之间有一个空行。 整个文件以两个-1结尾。
</dd> Output <dd> 对于输入的每一组数据，输出仅包括一行。如果该迷宫符合小希的思路，那么输出"Yes"，否则输出"No"。
</dd> Sample Input <dd>
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</dd> Sample Output <dd>
Yes Yes No</dd> <dd class="desc-container" style=""> {"safe":true,"sections": {"title":"","value":{"format":"HTML","content":"\u003cscript type\u003d\u0027text/x-mathjax-config\u0027\u003eMathJax.Hub.Config({tex2jax: { inlineMath: [[\u0027$\u0027,\u0027$\u0027],[\u0027\\[\u0027,\u0027\\]\u0027]] } }); \u003c/script\u003e\n\u003cscript type\u003d\u0027text/javascript\u0027 src\u003d\u0027https://cdn.mathjax.org/mathjax/latest/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\u0027\u003e\u003c/script\u003e\n\u003cscript type\u003d\u0027text/javascript\u0027\u003esetTimeout(function(){MathJax.Hub.Queue([\u0027Typeset\u0027, MathJax.Hub, \u0027left_view\u0027]);}, 2000);\u003c/script\u003e\n\u003cdiv class\u003d\"panel_content\"\u003e\n 上次Gardon的迷宫城堡小希玩了很久（见Problem B），现在她也想设计一个迷宫让Gardon来走。但是她设计迷宫的思路不一样，首先她认为所有的通道都应该是双向连通的，就是说如果有一个通道连通了房间A和B，那么既可以通过它从房间A走到房间B，也可以通过它从房间B走到房间A，为了提高难度，小希希望任意两个房间有且仅有一条路径可以相通（除非走了回头路）。小希现在把她的设计图给你，让你帮忙判断她的设计图是否符合她的设计思路。比如下面的例子，前两个是符合条件的，但是最后一个却有两种方法从5到达8。 \n \u003cbr\u003e \n \u003cimg style\u003d\"max-width:100%;\" src\u003d\"https://odzkskevi.qnssl.com/ce3d27d9f95d7ac87d47240232e2e0ba?v\u003d1488259874\" SRC\u003d\"https://odzkskevi.qnssl.com/ce3d27d9f95d7ac87d47240232e2e0ba?v\u003d1488259874\"\u003e \n \u003cbr\u003e \n\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"输入包含多组数据，每组数据是一个以0 0结尾的整数对列表，表示了一条通道连接的两个房间的编号。房间的编号至少为1，且不超过100000。每两组数据之间有一个空行。 \n\u003cbr\u003e整个文件以两个-1结尾。 \n\u003cbr\u003e"}},{"title":"Output","value":{"format":"HTML","content":"对于输入的每一组数据，输出仅包括一行。如果该迷宫符合小希的思路，那么输出\"Yes\"，否则输出\"No\"。 \n\u003cbr\u003e"}},{"title":"Sample Input","value":{"format":"HTML","content":"\u003cpre\u003e6 8 5 3 5 2 6 4\r\n5 6 0 0\r\n\r\n8 1 7 3 6 2 8 9 7 5\r\n7 4 7 8 7 6 0 0\r\n\r\n3 8 6 8 6 4\r\n5 3 5 6 5 2 0 0\r\n\r\n-1 -1\u003c/pre\u003e"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003cpre\u003eYes\r\nYes\r\nNo\u003c/pre\u003e"}},{"title":"Hint","value":{"format":"HTML","content":""}}{"title":"","value":{"format":"HTML","content":"\u003cscript type\u003d\u0027text/x-mathjax-config\u0027\u003eMathJax.Hub.Config({tex2jax: { inlineMath: [[\u0027$\u0027,\u0027$\u0027],[\u0027\\[\u0027,\u0027\\]\u0027]] } }); \u003c/script\u003e\n\u003cscript type\u003d\u0027text/javascript\u0027 src\u003d\u0027https://cdn.mathjax.org/mathjax/latest/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\u0027\u003e\u003c/script\u003e\n\u003cscript type\u003d\u0027text/javascript\u0027\u003esetTimeout(function(){MathJax.Hub.Queue([\u0027Typeset\u0027, MathJax.Hub, \u0027left_view\u0027]);}, 2000);\u003c/script\u003e\n\u003cdiv class\u003d\"panel_content\"\u003e\n 上次Gardon的迷宫城堡小希玩了很久（见Problem B），现在她也想设计一个迷宫让Gardon来走。但是她设计迷宫的思路不一样，首先她认为所有的通道都应该是双向连通的，就是说如果有一个通道连通了房间A和B，那么既可以通过它从房间A走到房间B，也可以通过它从房间B走到房间A，为了提高难度，小希希望任意两个房间有且仅有一条路径可以相通（除非走了回头路）。小希现在把她的设计图给你，让你帮忙判断她的设计图是否符合她的设计思路。比如下面的例子，前两个是符合条件的，但是最后一个却有两种方法从5到达8。 \n \u003cbr\u003e \n \u003cimg style\u003d\"max-width:100%;\" src\u003d\"https://odzkskevi.qnssl.com/ce3d27d9f95d7ac87d47240232e2e0ba?v\u003d1488259874\" SRC\u003d\"https://odzkskevi.qnssl.com/ce3d27d9f95d7ac87d47240232e2e0ba?v\u003d1488259874\"\u003e \n \u003cbr\u003e \n\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"输入包含多组数据，每组数据是一个以0 0结尾的整数对列表，表示了一条通道连接的两个房间的编号。房间的编号至少为1，且不超过100000。每两组数据之间有一个空行。 \n\u003cbr\u003e整个文件以两个-1结尾。 \n\u003cbr\u003e"}},{"title":"Output","value":{"format":"HTML","content":"对于输入的每一组数据，输出仅包括一行。如果该迷宫符合小希的思路，那么输出\"Yes\"，否则输出\"No\"。 \n\u003cbr\u003e"}},{"title":"Sample Input","value":{"format":"HTML","content":"\u003cpre\u003e6 8 5 3 5 2 6 4\r\n5 6 0 0\r\n\r\n8 1 7 3 6 2 8 9 7 5\r\n7 4 7 8 7 6 0 0\r\n\r\n3 8 6 8 6 4\r\n5 3 5 6 5 2 0 0\r\n\r\n-1 -1\u003c/pre\u003e"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003cpre\u003eYes\r\nYes\r\nNo\u003c/pre\u003e"}},{"title":"Hint","value":{"format":"HTML","content":""}}}#include<stdio.h> #include<string.h> #include<math.h> #include<stdlib.h> #include<algorithm> #include<iostream> #include<queue> using namespace std; int a[100005]; void s() { for(int i=0;i<100000;i++) { a[i] = i; } } int find(int x) { if (a[x] == x) { return x; } else { return a[x]=find(a[x]); } } int main() { int n1, n2; while (cin >> n1 >> n2) { if (n1 == -1) { break; } int maxnum = 0; s(); bool judge = true; while (n1 !=0 && n2 != 0) { n1 > n2 ? maxnum = n1 : maxnum = n2; if (find(n1) == find(n2)) { judge = false; } else { a[find(n1)] = a[find(n2)]; } cin >> n1 >> n2; } //判断是否所有出现过的房间都相通 int temp=0; for (int i = 0; i <= maxnum; i++) { if (a[i] != i) { if (temp == 0) { temp = find(a[i]); } else { if (temp != find(a[i])) { judge = false; } } } } if(judge) { cout << "Yes\n"; } else { cout << "No\n"; } } return 0; }
//byswust tp
盒马工作强度 28人发布