HDU 1878 欧拉回路（判断欧拉回路）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1878

题目大意：欧拉回路是指不令笔离开纸面，可画过图中每条边仅一次，且可以回到起点的一条回路。现给定一个图，问是否存在欧拉回路？

解题思路：判断无向图是否存在欧拉回路，判断每个点的度数是否为偶数+并查集确认连通性。

代码：

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #define CLR(arr,val) memset(arr,val,sizeof(arr))

 using namespace std;

 const int N=1e3+;

 int n,m;

 int root[N],indeg[N],outdeg[N];

 int find(int x){

     return root[x]==x?x:root[x]=find(root[x]);

 }

 int main(){

     while(scanf("%d",&n)!=EOF){

         if(n==)

             break;

         CLR(indeg,);

         CLR(outdeg,);

         for(int i=;i<=n;i++)

             root[i]=i;

         scanf("%d",&m);

         int a,b,x,y;

         for(int i=;i<=m;i++){

             scanf("%d%d",&a,&b);

             indeg[b]++;

             outdeg[a]++;

             x=find(a),y=find(b);

             if(x!=y)

                 root[x]=y;

         }

         bool flag=true;

         int cnt=;

         for(int i=;i<=n;i++){

             if(find(i)==i)

                 cnt++;

             if((indeg[i]+outdeg[i])%!=){

                 flag=false;

                 break;

             }

         }

         if(flag&&cnt==)

             puts("");

         else

             puts("");

     }

     return ;

 }