栾宫涅吧 关注:6贴子:216
  • 2回复贴,共1

HDU1272 小希的迷宫

只看楼主收藏回复

还是并查集的问题,只是数据要注意:
输入0 0,输出yes
迷宫裂开了输出No
#include <stdio.h>
#define MAXN 100001
int p[MAXN],num[MAXN];
int is(int a)
{
     if ((num[a]==1)&&(a==p[a])) return 0;
     else return 1;
}
int main()
{
     int a,b,pa,pb,i,uc,over=0;
     for (i=0;i<MAXN;i++)
     {
         p[i]=i;
         num[i]=1;
     }
     uc=0;
     while (scanf("%d%d",&a,&b)&&(a!=-1)&&(b!=-1))
     {
         if ((!a)&&(!b))
         {
             if (over || uc>1) printf("No\n");
             else printf("Yes\n");
             for (i=0;i<MAXN;i++)
             {
                 p[i]=i;
                 num[i]=1;
             }
             uc=0;
             over=0;
             continue;
         }
         if (!over)
         {
             pa=a;
             pb=b;
             while (pa!=p[pa]) pa=p[pa];
             while (pb!=p[pb]) pb=p[pb];
         }
         if (pa==pb)
         {
             over=1;
         }else
         if (num[pa]>=num[pb])
         {
             //printf("is(%d)=%d    is(%d)=%d\n",a,is(a),b,is(b));
             if ((!is(a))&&(!is(b)))



1楼2011-05-31 18:35回复
                 {
                     uc++;
                 }
                 else if (is(a)&&is(b))
                 {
                     uc--;
                 }
                 //printf("uc=%d\n",uc);
                 p[pb]=pa;
                 num[pa]+=num[pb];
             }
             else
             {
                 //printf("is(%d)=%d    is(%d)=%d\n",a,is(a),b,is(b));
                 if ((!is(a))&&(!is(b)))
                 {
                     uc++;
                 }
                 else if (is(a)&&is(b))
                 {
                     uc--;
                 }
                 //printf("uc=%d\n",uc);
                 p[pa]=pb;
                 num[pa]+=num[pb];
             }
         }
         return 0;
    }


    2楼2011-05-31 18:35
    回复


      来自手机贴吧3楼2012-09-22 18:40
      回复