首页 > 代码库 > hdu-1272 小希的迷宫

hdu-1272 小希的迷宫

题目传送门

  基础的并查集,稍微改下模板就可以。

  要注意两个条件:

    ①判断合并的两个点根节点是否相同

    ②每个点能否全部连通

  好像还有个问题,Yes 和 No。一开始把Yes和No全部都大写了,WA了几发  (..??_??..) 感觉应该不会有跟我一样的....

#include <iostream>
using namespace std;
int size[100010],tree[100010],vis[100010];
bool flag=true;
void makeSet(int x)
{
    size[x]=1;
    tree[x]=x;
    vis[x]=0;
}
int findSet(int x)
{
    if(x!=tree[x])
        tree[x]=findSet(tree[x]);
    return tree[x];
}
void Union(int x,int y)
{
    int fx=findSet(x);
    int fy=findSet(y);
    if(fx==fy)
    {
        flag=false;
        return;    
    }
    if(size[fx]<size[fy])            
    {
        tree[fx]=fy;
        size[fy]+=size[fx];
    }
    else
    {
        tree[fy]=fx;
        size[fx]+=size[fy];
    }
}
int main(void)
{
    int a,b;
    for(int i=0;i<100010;i++)
        makeSet(i);
    while(cin>>a>>b&&(a!=-1&&b!=-1))
    {
        if(a==0&&b==0)
        {
            int k=0;
            for(int i=1;i<100010;i++)
                if(tree[i]==i&&vis[i]!=0)
                    k++;
            if(k>1)
                flag=false;
            if(flag)
                cout<<"Yes"<<endl;
            else
                cout<<"No"<<endl;
            for(int i=0;i<100010;i++)
                makeSet(i);
            flag=true; 
        }
        if(a!=b)
        {
            Union(a,b);
            vis[a]=1;
            vis[b]=1;
        }    
    }
    return 0;
}

 

hdu-1272 小希的迷宫