首页 > 代码库 > hdu 1272 小希的迷宫(并查集 最小生成树)
hdu 1272 小希的迷宫(并查集 最小生成树)
http://acm.hdu.edu.cn/showproblem.php?pid=1272
这题要求任意两个房间都相通又不能有环
即通过并查集求出是否构成最小生成树
#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>using namespace std;#define maxn 100000int fa[maxn+10];int num[maxn+10];int vis[maxn+10];int ans,coun;int find(int x){ return fa[x]=(x==fa[x]?x:find(fa[x]));}void fun(int x,int y){ int fx=find(x); int fy=find(y); if(fx==fy) { ans=0; return ; } if(vis[x]==0) {vis[x]++;coun++;} if(vis[y]==0) {vis[y]++;coun++;} fa[fx]=fa[fy]; num[fy]+=num[fx]; if(num[fy]>ans) ans=num[fy];}int main(){ int n; int l,r; int i,j,k; while(scanf("%d%d",&l,&r)!=EOF) { if(l==0&&r==0) {printf("Yes\n"); continue;} if(l==-1&&r==-1) break; ans=1; coun=0; for(i=0;i<=maxn;i++) {fa[i]=i;num[i]=1;} memset(vis,0,sizeof(vis)); while(l!=0||r!=0) { if(ans) fun(l,r); scanf("%d%d",&l,&r); } if(ans==coun) printf("Yes\n"); else printf("No\n"); } return 0;}
hdu 1272 小希的迷宫(并查集 最小生成树)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。