HDOJ 1878 – 欧拉回路 判断无向图是否是欧拉图…

           无向图是欧拉图的充要条件是所有点的度为偶数并且所有点联通

           PS: 有向图是欧拉图的充要条件是所有点的入度=出度..并且联通…

Program:

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<cmath>
#include<queue>
#include<stack>
#include<set>
#include<time.h>
#include<map>
#include<algorithm>
#define ll long long
#define eps 1e-5
#define oo 1000000007
#define pi acos(-1.0)
#define MAXN 1050
#define MAXM 500005
using namespace std; 
int d[MAXN],father[MAXN];
int getfather(int x)
{
       if (father[x]==x) return x;
       return father[x]=getfather(father[x]);
}
int main()
{        
       int n,m,x,y,i;  
       while (~scanf("%d",&n) && n)
       {
                scanf("%d",&m);
                memset(d,0,sizeof(d));
                for (i=1;i<=n;i++) father[i]=i;
                while (m--)
                {
                       scanf("%d%d",&x,&y);
                       d[x]++,d[y]++;
                       x=getfather(x),y=getfather(y);
                       father[x]=y;
                }
                for (i=1;i<=n;i++)
                   if (d[i]%2 || getfather(i)!=father[1]) break;
                if (i<=n) printf("0\n"); 
                    else  printf("1\n");
       }
       return 0;
}