首页 > 代码库 > 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 小希的迷宫(并查集 最小生成树)