题目连接
http://acm.hdu.edu.cn/showproblem.php?pid=1878
欧拉回路
Description
欧拉回路是指不令笔离开纸面，可画过图中每条边仅一次，且可以回到起点的一条回路。现给定一个图，问是否存在欧拉回路？
Input
测试输入包含若干测试用例。每个测试用例的第1行给出两个正整数，分别是节点数$N ( 1 < N < 1000 )$和边数$M$；随后的$M$行对应$M$条边，每行给出一对正整数，分别是该条边直接连通的两个节点的编号（节点从1到$N$编号）。当$N$为0时输入结
束。
Output
每个测试用例的输出占一行，若欧拉回路存在则输出1，否则输出0。
Sample Input
3 3
1 2
1 3
2 3
3 2
1 2
2 3
0
Sample Output
1
0
判断一张图是否存在欧拉回路。。
1 #include<algorithm> 2 #include<iostream> 3 #include<cstdlib> 4 #include<cstring> 5 #include<cstdio> 6 #include<vector> 7 #include<map> 8 using std::map; 9 using std::cin; 10 using std::cout; 11 using std::endl; 12 using std::find; 13 using std::sort; 14 using std::pair; 15 using std::vector; 16 using std::multimap; 17 #define pb(e) push_back(e) 18 #define sz(c) (int)(c).size() 19 #define mp(a, b) make_pair(a, b) 20 #define all(c) (c).begin(), (c).end() 21 #define iter(c) decltype((c).begin()) 22 #define cls(arr,val) memset(arr,val,sizeof(arr)) 23 #define cpresent(c, e) (find(all(c), (e)) != (c).end()) 24 #define rep(i, n) for (int i = 0; i < (int)(n); i++) 25 #define tr(c, i) for (iter(c) i = (c).begin(); i != (c).end(); ++i) 26 const int N = 1010; 27 typedef unsigned long long ull; 28 struct Node { int to, next; }; 29 struct Euler { 30 Node G[N]; 31 bool vis[N]; 32 int tot, inq[N], head[N]; 33 inline void init() { 34 tot = 0; 35 cls(vis, false), cls(inq, 0), cls(head, -1); 36 } 37 inline void add_edge(int u, int v) { 38 G[tot].to = v; G[tot].next = head[u]; head[u] = tot++; 39 } 40 inline void dfs(int u) { 41 vis[u] = true; 42 for (int i = head[u]; ~i; i = G[i].next) { 43 if (!vis[G[i].to]) dfs(G[i].to); 44 } 45 } 46 inline void work(int n, int m) { 47 init(); 48 int u, v; 49 bool f = true; 50 rep(i, m) { 51 scanf("%d %d", &u, &v); 52 inq[u]++, inq[v]++; 53 add_edge(u, v), add_edge(v, u); 54 } 55 rep(i, n) { 56 if (inq[i + 1] & 1) { f = false; break; } 57 } 58 if (!f) { puts("0"); return; } 59 dfs(1); 60 rep(i, n) { 61 if (!vis[i + 1]) { f = false; break; } 62 } 63 puts(f ? "1" : "0"); 64 } 65 }go; 66 int main() { 67 #ifdef LOCAL 68 freopen("in.txt", "r", stdin); 69 freopen("out.txt", "w+", stdout); 70 #endif 71 int n, m; 72 while (~scanf("%d", &n), n) { 73 scanf("%d", &m); 74 go.work(n, m); 75 } 76 return 0; 77 }