最新消息:热烈庆祝IT小记上线!

HDU 1272 小希的迷宫(并查集)

先写上AC代码。回头再来进行解释。。。

#include<stdio.h>
#include<string.h>
#include<iostream>
#define maxn 100010
using namespace std;

int pre[maxn];
int t[maxn];//把出现的数都存入这个数组 
int q[maxn];//标记有没有出现过的数 

int find(int x)//查找树根 
{
    if(pre[x]==0) return x;
    return pre[x]=find(pre[x]);
}    

int main()
{
    int cnt;
    int a,b;
    bool flag;
    while(scanf("%d%d",&a,&b))
    {
        if(a==-1&&b==-1) break; 
        if(a==0&&b==0)
        {
            printf("Yes\n");
            continue;
        }    
        memset(pre,0,sizeof(pre));
        memset(q,0,sizeof(q));
        cnt=0;
        pre[a]=b;
        if(q[a]==0)
        {
            q[a]=1;
            t[cnt++]=a;
        }    
        if(q[b]==0)
        {
            q[b]=1;
            t[cnt++]=b;
        }    
        flag=true;
        while(scanf("%d%d",&a,&b))
        {
            if(a==0&&b==0) break;

            if(flag==false)continue;

            int t1=find(a);
            int t2=find(b);
            if(t1==t2) 
            {
                flag=false;
                continue;
            }    
            else pre[t1]=t2;
            if(q[a]==0)
            {
               q[a]=1;
               t[cnt++]=a;
            }    
            if(q[b]==0)
            {
                q[b]=1;
                t[cnt++]=b;
            }   
        }       
        if(flag==true)
        {
            int temp=0;
            for(int i=0;i<cnt;i++)
            {
                if(pre[t[i]]==0) temp++;
            }
            if(temp>1) flag=false;

        }    
        if(flag==true) printf("Yes\n");
        else printf("No\n");
    }    
    return 0;
}

猜您喜欢

备案号:苏ICP备12016861号-4