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

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

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

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

代码：

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 #define CLR(arr,val) memset(arr,val,sizeof(arr))
 5 using namespace std;
 6 const int N=1e3+5;
 7 
 8 int n,m;
 9 int root[N],indeg[N],outdeg[N];
10 
11 int find(int x){
12     return root[x]==x?x:root[x]=find(root[x]);
13 }
14 
15 int main(){
16     while(scanf("%d",&n)!=EOF){
17         if(n==0)
18             break;        
19         CLR(indeg,0);
20         CLR(outdeg,0);
21         for(int i=1;i<=n;i++)
22             root[i]=i;
23         scanf("%d",&m);
24         int a,b,x,y;
25         for(int i=1;i<=m;i++){
26             scanf("%d%d",&a,&b);
27             indeg[b]++;
28             outdeg[a]++;
29             x=find(a),y=find(b);
30             if(x!=y)
31                 root[x]=y;
32         }
33         bool flag=true;
34         int cnt=0;
35         for(int i=1;i<=n;i++){
36             if(find(i)==i)
37                 cnt++;
38             if((indeg[i]+outdeg[i])%2!=0){
39                 flag=false;
40                 break;
41             }
42         }
43         if(flag&&cnt==1)
44             puts("1");
45         else
46             puts("0");
47     }
48     return 0;
49 }