Loading......Next.

生来介为忙一场

 

欧拉回路问题~

hdoj 1878 和 http://acm.nyist.net/JudgeOnline/problem.php?pid=42
主要是将一小块一小块的东西合起来

#include<stdio.h>
#include<string.h>
int d[1001],set[1001];
int w;
int find(int x)
{
    int i,j,r=x;
    while(r!=set[r]) r=set[r];//根节点 
/*    i=x;
    while(i!=r)
    {
        j=set[i];
        set[i]=r;
        i=j;
    }*/
    return r;
}
void unio(int x,int y)
{
    x=find(x);
    y=find(y);
    if(x>y) set[x]=y;
    else set[y]=x;
    if(x!=y) w--;
}
int main()
{
   int n,p,q,i;
   int a,b,flag,k,j;
   scanf("%d",&n);
   while(n--)
   {
   scanf("%d %d",&p,&q);
   w=p;
   memset(d,0,sizeof(d));
   flag=0;
    for(i=1;i<=p;i++) set[i]=i;
   while(q--)
  {
    scanf("%d %d",&a,&b);
    if(a!=b)
    {
    d[a]++;d[b]++;
    unio(a,b);
    }
  }
  k=0;
  for(i=1;i<=p;i++)
  {
   if(d[i]&1) k++;
   if(d[i]==0) 
   {
    k=1;
    break;
   }
  }
if(flag||(k!=0&&k!=2)||w!=1) printf("No\n");
else printf("Yes\n");
}
return 0;
}


posted on 2011-12-11 16:33 bersaty 阅读(210) 评论(0)  编辑 收藏 引用 所属分类: 并查集


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理


导航

统计

常用链接

留言簿

随笔分类

随笔档案

友情链接

搜索

最新评论

阅读排行榜

评论排行榜