题目链接:https://uva.onlinejudge.org/external/100/10054.pdf
题目链接:http://vjudge.net/contest/132239#problem/C
欧拉回路公式:
1、图是连通的。
2、所有点的度都是偶数。
tip: 网上有很多解法,几乎都是一样,由于UVa的数据都是连通的,几乎都没有判连通。
#include <stdio.h> #include <string.h> #include <bits/stdc++.h> using namespace std; #define N 55 #define MAX 1010 int g[N][N],vis[N]; int d[N]; int n; void euler(int u) { int v; for(v=1; v<=50; v++) if(g[u][v]) { g[u][v]--; g[v][u]--; euler(v); printf("%d %d ",v,u); } } void dfs(int k) { vis[k] = true; for(int i=1; i<=50; i++) { if(g[k][i]) { if(!vis[i]) dfs(i); } } } int main() { //freopen("input.txt","r",stdin); int t,T; int i; int u,v; scanf("%d",&T); vector<int> Q; for(t=1 ; t<=T; t++) { memset(g,0,sizeof(g)); memset(vis,0,sizeof(vis)); memset(d,0,sizeof(d)); Q.clear(); scanf("%d",&n); for(i=1 ; i<=n; i++) { scanf("%d%d",&u,&v); d[u]++; d[v]++; g[u][v]++; g[v][u]++; Q.push_back(u); Q.push_back(v); } printf("Case #%d ",t); dfs(Q[0]); bool flag = true; for(i=0; i<Q.size(); i++) { if(!vis[Q[i]]) { flag = false; break; } } if(!flag) { printf("some beads may be lost "); if(t!=T) printf(" "); } //图是连通的,要判断所有点的度是否有为偶数 else { for(i=1 ; i<=50; i++) if(d[i]%2) break; if(i<=50) printf("some beads may be lost "); else //图连通而且所有点的度都为偶数,则是一个欧拉回路,输出路径 for(i=1; i<=50; i++) euler(i); if(t!=T) printf(" "); } } return 0; }