hdu 1878欧拉回路

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

View Code

 1 #include<stdio.h>
 2 #include<string.h>
 3 int n,m;
 4 int root[1002];
 5 int from[1002];
 6 int to[1002];
 7 int  find(int x)
 8 {
 9     int res=x;
10     while(x!=root[x])
11     x=root[x];
12     return x;
13 }
14 
15 void merge(int x,int y)
16 {
17     
18     int fx,fy;
19     fx=find(x);
20     fy=find(y);
21     if(fx!=fy) root[fx]=fy;
22 }
23 int main()
24 {
25     int a,b;
26     while(~scanf("%d",&n),n)
27     {
28         for(int i=1;i<=n;i++)
29         root[i]=i;
30         memset(from,0,sizeof(from));
31         memset(to,0,sizeof(to));
32         scanf("%d",&m);
33         for(int i=0;i<m;i++)
34         {
35             scanf("%d%d",&a,&b);
36             merge(a,b);
37             from[a]++;
38             from[b]++;
39         }
40         int flag=0;
41         int count=0;
42         for(int i=1;i<=n;i++)
43         {
44             if(from[i]%2)
45             {
46                 flag=1;
47                 break;
48             }
49             if(find(i)==i) count++; 
50         }
51         if(count==1&&flag==0) printf("1\n");
52         else printf("0\n"); 
53     }
54     
55 }

欧拉回路：每个点的入度和出度均为偶数。