现在的位置: 首页 > 综合 > 正文

hdu 1272

2013年08月06日 ⁄ 综合 ⁄ 共 938字 ⁄ 字号 评论关闭

又是一个并查序的问题,这里有两方面

1:必须是并查集

2:满足点的个数比边数多一

URL:http://acm.hdu.edu.cn/showproblem.php?pid=1272

代码如下

#include<stdio.h>
#include<algorithm>
#define M 100010
using namespace std;
int father[M], mark[M];
int flag;
void init()
{
   for(int i=0;i<M;i++)
    {
      father[i]=i;
      mark[i]=0;
    }
}
int getfather(int r)
{
    int n=r;
    while(n!=father[n])
       n=father[n];
    return n;
}
void Union(int x,int y)
{
    int rootx=getfather(x);
    int rooty=getfather(y);
    if(rootx!=rooty)
      father[rootx]=rooty;
}
int main()
{
    int a,b,i;
    while(scanf("%d%d",&a,&b)!=EOF && (a!=-1 || b!=-1))
    {
          if(a==0 && b==0)
            {
               printf("Yes\n");
               continue;
            }
            init();
            int max=-1,min=M,num=0;
            flag=0;
            while(a||b)
            {
              if(a>max) max=a;
              if(b>max) max=b;
              if(a<min) min=a;
              if(b<min) min=b;
              mark[a]=1;mark[b]=1;
              int aa=getfather(a);
              int bb=getfather(b);
              if(aa==bb)
                  flag=1;
              else
                   Union(aa,bb);
            scanf("%d%d",&a,&b);
            }
            if(flag==1)
               printf("No\n");
            else
            {
                for(i=min;i<=max;i++)  //  这里的min和max就是上面的计算的范围,减少没必要的搜索
                {
                    if(mark[i]==1 && father[i]==i)  //  mark就是说在for循环里面有这个数字
                      num++;
                }
                if(num==1)
                  printf("Yes\n");
                else
                 printf("No\n");
            }
    }
    return 0;
}

抱歉!评论已关闭.