(UPD 这篇里面写的代码是可以退化成O(n^2)的。。。当时比较弱）

2007《欧拉回路性质与应用探究》

·欧拉回路：经过每条边仅一次的回路
欧拉路径：经过每条边仅一次的路径

·存在欧拉回路的充要条件：
无向图：连通。每个点度数为偶数
有向图：基图（即无向版本）连通。每个点入度等于出度
·存在欧拉路径但不存在欧拉回路的充要条件
无向图：连通。除两个点度数为奇数外，其他点度数为偶数
有向图：基图连通。一个点的入度等于出度+1，一个点的出度等于入度+1，其他点入度等于出度
水题HDU1878：无向图的欧拉回路是否存在。是否连通用并查集判，然后统计一下度数即可。
HDU1116:单词接龙，论文上的例题。有向边表示单词，两个结点分别代表首尾字母。判欧拉回路。
HDU3018：判断一个无向图至少需要几笔画成。分别考虑每个连通分量：如果是欧拉图则需1笔，如果有两个奇点也只需1笔，否则记奇点个数为k（易证这个k一定是偶数），则需要k/2笔。因为每一笔路径可以消除两个奇点。

·求无向图的欧拉回路
在保证欧拉回路存在的情况下（需要事先判断），可以DFS求得欧拉回路。

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
struct edge{int v,next,vis;}e[1000];int etot;
int g[1000];int n,m;
void ae(int u,int v){
	e[etot].v=v;e[etot].vis=0;e[etot].next=g[u];g[u]=etot++;
	e[etot].v=u;e[etot].vis=0;e[etot].next=g[v];g[v]=etot++;
}
int stk[1000];int top=0;
void dfs(int u){
	for (int i=g[u];~i;i=e[i].next)if(!e[i].vis){
		e[i].vis=e[i^1].vis=1;
		dfs(e[i].v);
		stk[++top]=i;
	}
}		
int main()
{
	memset(g,-1,sizeof(g));etot=0;
	scanf("%d%d",&n,&m);
	while(m--){
		int u,v;
		scanf("%d%d",&u,&v);
		ae(u,v);
	}
	dfs(1);
	for (int i=top;i>=1;i--)printf("%d->%d\n",e[stk[i]^1].v,e[stk[i]].v);
	return 0;
}

·求有向图的欧拉回路
类似上面的DFS。无向的两条边改为一条即可。
·求无向图的欧拉路径
同上，但DFS起点必须是图中的一个奇点
·求有向图的欧拉路径
同上，但DFS起点必须是满足出度=入度+1的那个点

·非递归版本
自己手写一个栈替代系统栈

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
struct edge{int v,next,vis;}e[1000];int etot;
int g[1000];int n,m;
void ae(int u,int v){
	e[etot].v=v;e[etot].vis=0;e[etot].next=g[u];g[u]=etot++;
	e[etot].v=u;e[etot].vis=0;e[etot].next=g[v];g[v]=etot++;
}
int stk[1000];int top=0;
int sysstk[1000],inedge[1000],cur[1000];int systop=0;
void dfs(int st){
	sysstk[++systop]=st;cur[systop]=g[st];
	while(systop){		
		if(cur[systop]==-1){			
			if(systop!=1)stk[++top]=inedge[systop];
			systop--;
		}else{
			int i=cur[systop];cur[systop]=e[cur[systop]].next;
			if(!e[i].vis){
				e[i].vis=e[i^1].vis=1;
				sysstk[++systop]=e[i].v;cur[systop]=g[e[i].v];inedge[systop]=i;
			}			
		}
	}
}
int main()
{
	memset(g,-1,sizeof(g));etot=0;
	scanf("%d%d",&n,&m);
	while(m--){
		int u,v;
		scanf("%d%d",&u,&v);
		ae(u,v);
	}
	dfs(1);
	for (int i=top;i>=1;i--)printf("%d->%d\n",e[stk[i]^1].v,e[stk[i]].v);
	return 0;
}

·中国邮路问题
带边权无向图，从某个点出发并最终回到这个点，要求每条边至少走过一次。求最小总路程。
首先必须得是连通图。算出每对奇点之间的最短路径，做一次最小权匹配（费用流/KM），把匹配边添加到原图上去，这时图上就全是偶点了，求欧拉回路即可。
·中国邮路问题有向版本
首先必须得是强连通图。记d(v)=d的入度-d的出度。建立超级源S、超级汇T。原图中的边费用设为边权，容量为INF。对于d(v)>0的点v，由S连向v，费用为0，容量为d(v)；对于d(v)<0的点v，由v连向T，费用为0，容量为-d(v)。求最小费用最大流。然后对于有流量的边(u,v)，在原图中再添加f(u,v)次重边。求欧拉回路即可。

·随机欧拉图
搜到一篇论文http://compalg.inf.elte.hu/~tony/Oktatas/TDK/FINAL/Chap%203.PDF
如果在图G上从点v开始，沿着未访问过的边随意行走，最终总能形成一条欧拉回路，那么称图G由v“任意可遍历”（好奇怪的术语）。
图G由v任意可遍历的充要条件是图G中的所有环都经过v。