欧拉回路：图G，若存在一条路，经过G中每条边有且仅有一次，称这条路为欧拉路，如果存在一条回路经过G每条边有且仅有一次，称这条回路为欧拉回路。具有欧拉回路的图成为欧拉图。
判断欧拉路是否存在的方法
有向图：图连通，有一个顶点出度大入度1，有一个顶点入度大出度1，其余都是出度=入度。
无向图：图连通，只有两个顶点是奇数度，其余都是偶数度的。
定理：无向图G具有一条欧拉路，当且仅当G是连通的，且有0个或者是两个奇数度得结点。
推论：无向图G具有一条欧拉回路，当且仅当G是连通的，并且所有结点的度数均为偶数。
判断欧拉回路是否存在的方法
有向图：图连通，所有的顶点出度=入度。
无向图：图连通，所有顶点都是偶数度。
定理：有向图G具有 单向欧拉路，当且仅当它是连通的，而且除两个结点外，每个结点的入度等于出度，但这两个结点中，一个结点的入度比出度大1，另一个结点的入度比出度小1。
定理：有向图G具有一条单向欧拉回路，当且仅当是连通的，且每个结点入度等于出度。
程序实现一般是如下过程：
1.利用并查集判断图是否连通，即判断p[i] < 0的个数，如果大于1，说明不连通。
2.根据出度入度个数，判断是否满足要求。
3.利用dfs输出路径。
找欧拉回路：根据DFS（边）的性质，回溯是记录，可以求出欧拉回路。有向图与无向图的区别就是在DFS时，要标记的边，有向图标记一条就足以，而无向图需要将两条都标记。找欧拉通路原理与回路相同，代码也相同。
1 #include2 #include 3 #include 4 using namespace std; 5 6 int first[100]; 7 int next[100]; 8 int v[100]; 9 int d[100];10 int vis[100];11 int times;12 int n,m;13 14 void dfs(int start)15 {16 int i,j,k;17 for(k=first[start]; k!=-1; k=next[k])18 {19 if(vis[k]==0)20 {21 vis[k]=1;22 dfs(v[k]);23 int temp1=k%m;24 if(k%m==0)25 temp1=m;26 d[times++]=temp1;27 }28 }29 }30 int main()31 {32 int i,j,k;33 while(cin>>n>>m)34 { 35 memset(first,-1,sizeof(first));36 memset(next,-1,sizeof(next));37 memset(vis,0,sizeof(vis));38 times=1;39 d[0]=-1;40 int temp1,temp2,temp3;41 for(i=1; i<=m; i++)42 { 43 cin>>temp1>>temp2; 44 if(first[temp1]==-1)45 {46 first[temp1]=i;47 }48 else49 {50 temp3=first[temp1];51 first[temp1]=i;52 next[i]=temp3;53 }54 v[i]=temp2;55 } 56 dfs(1); 57 for(i=1; i