本文主要是介绍http://acm.hdu.edu.cn/showproblem.php?pid=1272，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目大意：小希要做一个迷宫，迷宫中任意两个房间有且仅有一条路径可以相通（除非走了回头路）。这样，就需要用到并查集了（赤裸裸的），对于输入的两个顶点，判断是否在同一个集合内，是的话，就是存在多条通路了，而对于一个迷宫，所有的点最后必须在同一个集合，处理好这两个问题，就可以了
有一个比较特殊的情况，就是输入的那一组数据只有两个0，必须输出 Yes
网上有很多人写了这个题目的解题报告，但大家都是用一个数组来记录是否用过，然后对用过的点进行寻根，最后看一下是不是所有有用过的点都是同一个根，我觉得没有必要，只要记录点是否用过，最后，连接得到的边和用到的点的差是1就可以了，也就是说连接n个点，只要n-1条边，O(∩_∩)O~、、
代码：
#include<iostream>
#define N 100001
#include<string.h>
#include<cstdio>
using namespace std;
int used[N],father[N];
int n,m;
int find_set(int a)
{//return a==father[a]?a:father[a]=find_set(father[a]);以开始用这个代码总是错误，后来改用下面的代码，果断AC不知为什么，望大牛指点。。。，，，
while(a!=father[a])a=father[a];return a;}
bool Union(int a,int b)
{ a=find_set(a);b=find_set(b);if(a==b) return false;father[a]=b;return true;
}
int main()
{ while(~scanf("%d%d",&n,&m)!=EOF&&(m+n!=-2)){ if(n==0&&m==0){ printf("Yes\n");continue;}memset(used,0,sizeof(used));for(int i=0;i<N;i++)father[i]=i;Union(n,m);used[n]=used[m]=1;int t=1,flag=1;while(~scanf("%d%d",&n,&m)!=EOF&&n&&m){ // if(n==0&&m==0) break;if(!used[n]) {t++;used[n]=1;}if(!used[m]) {t++;used[m]=1;}if(!Union(n,m)) flag=0;else t--;}if(flag&&t==1) printf("Yes\n");else printf("No\n");}return 0;}
这篇关于http://acm.hdu.edu.cn/showproblem.php?pid=1272的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
