hdu 1272 小希的迷宫

并查集 判断是否有环、未给出点数判断集合数是否大于1

就是判断是否是最小生成树吧

判断有环：

若输入两点的根相同则有环

判断所有点是否都在同一集合内：

此题有点不严谨吧，还是看了别人代码才知道，给的点是一个区间内的所有点。

合并过程中把出现的点都标记，把最小和最大的找到，枚举在该范围内的点，看有几个根，有几个根就有几个集合。

#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#define inf 0x3f3f3f3f
#define ll __int64
using namespace std;

int r[100005],n,m,ans,vis[100005];

int root(int a)
{
    if(r[a]==a) return a;
    else return r[a]=root(r[a]);
}

void merge(int a,int b)
{
    int ra,rb;
    ra=root(a);
    rb=root(b);
    if(ra==rb) ans=0;//有环
    else if(ra<rb)
        r[rb]=ra;
    else r[ra]=rb;
}

int main()
{
    int i,flag,minn,maxx,x,y;
    memset(vis,0,sizeof vis);
    for(i=0;i<=100000;i++)
        r[i]=i;
    ans=1;minn=100005;maxx=0;
    while(scanf("%d%d",&n,&m))
    {
        if(n==-1&&m==-1) break;
        if(n==0&&m==0)
        {
            for(flag=0,i=minn;i<=maxx;i++)//看是否所有点都在一个集合内
            {
                if(r[i]==i&&vis[i])
                    flag++;
                if(flag>1)
                {
                    ans=0;
                    break;
                }
            }
            if(ans)
                printf("Yes\n");
            else printf("No\n");

            for(i=0;i<=100000;i++)
                r[i]=i;
            memset(vis,0,sizeof vis);
            ans=1;minn=100005;maxx=0;
            continue;
        }
        x=min(n,m);
        y=max(n,m);
        minn=min(minn,x);
        maxx=max(maxx,y);
        vis[n]=1;
        vis[m]=1;
        merge(n,m);
    }
    return 0;
}

hdu 1272 小希的迷宫,布布扣,bubuko.com

hdu 1272 小希的迷宫

原文：http://blog.csdn.net/u011032846/article/details/20479959