本文主要是介绍HDU-1272 小希的迷宫 并查集，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接
#include "stdio.h"
const int maxn = 100050;
int p[maxn],rank[maxn];
bool vis[maxn];
int n,flag;
int find( int x )
{return p[x] == x ? x:p[x] = find(p[x]);
}
void merge( int a,int b )
{int x = find(a);int y = find(b);if( x!=y )if( rank[x] > rank[y] )p[y] = x;else{p[x] = y;if( rank[x] == rank[y] )rank[y]++;}elseflag = 0;
}
int main()
{int a,b;while( scanf("%d%d",&a,&b)==2 ,( a!=-1 || b!=-1 ) ){if( !a || !b ){puts("Yes");continue;}for( int i = 0; i < maxn; i ++ ){p[i]= i;vis[i]=0;rank[i] = 0;}vis[a] = vis[b] = 1;flag = 1;merge(a,b);while( scanf("%d%d",&a,&b)==2,(a||b) ){merge(a,b);vis[a] = vis[b] = 1;}int k = 0;for( int i = 1; i < maxn; i ++ ){if( vis[i] && p[i]==i ){k++;}if( k>1 )flag = 0;}if( flag )puts("Yes");elseputs("No");}return 0;
}这篇关于HDU-1272 小希的迷宫 并查集的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
