若图G中存在这样一条路径，从某个顶点出发，使得它恰通过G中每条边一次(通过每一个顶点可以多次),则称该路径为欧拉路径。若该路径是一个圈(回到起点)，则称为欧拉(Euler)回路。
欧拉回路与欧拉路径的充要条件：
1)无向图存在欧拉回路的充要条件:一个无向图存在欧拉回路，当且仅当该图所有顶点度数都为偶数,且该图是连通图。
2)有向图存在欧拉回路的充要条件:一个有向图存在欧拉回路，所有顶点的入度等于出度且该图是连通图。
判断无向图是否存在欧拉回路：(1)图联通(dfs或者并查集判图联通)(2)所有顶点的度数均是偶数
判断有向图是否存在欧拉回路：(1)底图(忽略边方向后的无向图)联通(2)每个顶点的入度等于出度
判断无向图是否存在欧拉路径：(1)图联通(dfs或者并查集判图联通)(2)仅有2个顶点(起点和终点)的度数为奇数，其他顶点的度数均是偶数。
判断有向图是否存在欧拉路径：(1)底图(忽略边方向后的无向图)联通(2)只有两个点的入度不等于出度，并且其中一个点出度恰好比入度大1，另一个恰好入度比出度小1，每个顶点其它每个点的入度等于出度
1.http://poj.org/problem?id=2230
本题目构建图时，每一对顶点添加两条方向相反的边。题目已经说一定具有回路，所以采用dfs从顶点1开始对边进行不重复的遍历一次即可，当所有边遍历完后，回到考虑起始点。
//---dfs求欧拉回路
#define _CRT_SECURE_NO_DEPRECATE
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int maxn = 10000 + 5;
struct edge{
int v;
bool vis;
edge(int i = 0) :v(i){ vis = 0; }
};
vector<edge>G[maxn];
void dfs(int u){
for (int i = 0; i < G[u].size(); i++){
edge &e = G[u][i];
if (!e.vis){
e.vis = true;
dfs(e.v);
}
}
printf("%d
", u);
}
int main(){
int u, v, m, n;
while (~scanf("%d%d", &n, &m)){
for (int i = 0; i <=n; i++)G[i].clear();
for (int i = 0; i < m; i++){
scanf("%d%d", &u, &v);
G[u].push_back(edge(v));
G[v].push_back(edge(u));
}
dfs(1);
}
return 0;
}
2.http://poj.org/problem?id=2337
首先用并查集判断是否可以构成欧拉回路。然后确定可以构成欧拉回路后再用dfs搜索出最小字典序点的欧拉道路。如果事先没有判断是否可以构成欧拉回路直接爆DFS来搜索，将会耗去大量时间。
//---dfs求欧拉回路
#define _CRT_SECURE_NO_DEPRECATE
#include<iostream>
#include<string.h>
#include<algorithm>
#include<vector>
using namespace std;
const int maxn = 1000 + 5;
const int maxsize = 26;
struct Edge{
Edge(int a = 0, int b = 0) :v(a), id(b), vis(0){}
int v;
int id;//char str[maxsize];
bool vis;
};
char str[maxn][maxsize];
int p[maxn];
int deg[26];
vector<Edge>G[maxsize];
int n;
bool ans;
int used[26];
int parent[26];
int getparent(int i){
if (parent[i] == -1)return i;
return parent[i] = getparent(parent[i]);
}
bool cmp(Edge a, Edge b){
return strcmp(str[a.id], str[b.id])<0;
}
void dfs(int u, int curr){
if (curr == n){
ans = 1;
printf("%s", str[p[0]]);
for (int i = 1; i < n; i++)printf(".%s",str[p[i]]);
printf("
");
return;
}
if (ans)return;
for (int i = 0; i < G[u].size(); i++){
Edge&e = G[u][i];
if (!e.vis){
e.vis = 1;
p[curr] = e.id;
dfs(e.v, curr + 1);
e.vis = 0; //撤回标志
}
}
}
int main(){
int T, i, u, v;
scanf("%d", &T);
while (T--){
memset(deg, 0, sizeof(deg));
memset(used, 0, sizeof(used));
memset(parent, -1, sizeof(parent));
for (i = 0; i < 26; i++)G[i].clear();
scanf("%d", &n);
int cc = 26;//联通块；
for (i = 0; i < n; i++){
scanf("%s", str[i]);
u = str[i][0] - 'a';
v = str[i][strlen(str[i]) - 1] - 'a';
deg[u]++; deg[v]--;
used[u] = used[v] = 1;
G[u].push_back(Edge(v, i));
u = getparent(u); v = getparent(v);
if (u != v){
cc--;
parent[u] = v;
}
}
vector<int>d;
for (i = 0; i < 26; i++){
if (!used[i])cc--;
else if (deg[i])d.push_back(deg[i]);
}
ans = 0;
if (cc == 1 && (d.empty() || d.size() == 2 && (d[0] == -1 || d[0] == 1)))ans = 1;
if (ans == 0){
printf("***
"); continue;
}
for (i = 0; i < 26; i++)
sort(G[i].begin(), G[i].end(), cmp);
if (d.size() == 2){
for (i = 0; i < n; i++){
if (deg[i] == 1)break;
}
}
else{
i = 0;
while (!used[i])i++;
}
ans = 0;
dfs(i, 0);
}
return 0;
}