欧拉回路：图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 #include<iostream> 2 #include <cstring> 3 #include<queue> 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 else 49 { 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<times; i++) 58 cout<<d[i]<<" "; 59 cout<<endl; 60 } 61 return 0; 62 } 63
