HDU 1878 欧拉回路

本文链接:http://www.cnblogs.com/Ash-ly/p/5405580.html

题意：

　　欧拉回路是指不令笔离开纸面，可画过图中每条边仅一次，且可以回到起点的一条回路。现给定一个图，问是否存在欧拉回路？若欧拉回路存在则输出1，否则输出0。

思路：

　　由题意可知，这是一个无向图，无向图存在欧拉回路需要满足两个条件：

　　1：底图是连通的，可用并查集判断。

　　2：不存在度数为奇数的点。

　　由上述两个条件可直接判断。

代码：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cstdlib>
 5 #include <cmath>
 6 #include <algorithm>
 7 #include <stack>
 8 #include <queue>
 9 using namespace std;
10 
11 const int maxV = 1000;
12 const int maxE = maxV * maxV / 2 + 7;
13 int degree[maxV + 7];
14 int pre[maxV + 7];
15 int E, V;
16 
17 void initPre()
18 {
19     for(int i = 1; i <= maxV; i++)pre[i] = i;
20 }
21 
22 int Find(int x)
23 {
24     return x == pre[x] ? x : pre[x] = Find(pre[x]);
25 }
26 
27 void mix(int x, int y)
28 {
29     int fx = Find(x);
30     int fy = Find(y);
31     if(fx != fy) pre[fx] = fy;
32 }
33 
34 int isEuler()
35 {
36     for(int i = 1; i <= V; i++)
37         if(degree[i] & 1) return 0;
38     return 1;
39 }
40 
41 int isConnct()
42 {
43     int cnt = 0;
44     for(int i = 1; i <= V; i++)
45         if(pre[i] == i) cnt++;
46     if(cnt == 1) return 1;
47     return 0;
48 }
49 
50 int main()
51 {
52     //freopen("in.txt", "r", stdin);
53     while(~scanf("%d", &V) && V)
54     {
55         scanf("%d", &E);
56         memset(degree, 0, sizeof(degree));
57         initPre();
58         for(int i = 1; i <= E; i++)
59         {
60             int fr, to;
61             scanf("%d%d", &fr, &to);
62             degree[fr]++;
63             degree[to]++;
64             mix(fr, to);
65         }
66         if(isConnct() && isEuler())printf("1
");
67         else printf("0
");
68     }
69     return 0;
70 }