如果一个图存在一笔画，则一笔画的路径叫做欧拉路，如果最后又回到起点，那么这个路径叫做欧拉回路。
这里有一个定义：奇点指跟这点相连的边数有奇数个的点，反之，有偶数个则称为偶点。
那么如何在一个图里寻找欧拉（回）路，存在两个定理：
1.存在欧拉路的条件：图是连通的，有且只有两个奇点
2.存在欧拉回路的条件：图是连通的，有0个奇点
所以，要寻找欧拉回路，对任意一个点执行深度优先遍历即可；寻找欧拉回路，则对一个奇点执行深度优先遍历，时间复杂度为O(m+n)。
代码：
1 #include<iostream> 2 #include<cstring> 3 using namespace std; 4 #define maxn 101 5 int g[maxn][maxn],du[maxn],circuit[maxn]; 6 int n,e,circuitpos,i,j,x,y,start; 7 void find_circuit( int i) 8 { 9 for(j=1;j<=n;j++) 10 if(g[i][j]==1) 11 { 12 g[i][j]=g[j][i]=0; 13 find_circuit(j); 14 } 15 circuit[++circuitpos]=i; 16 } 17 int main() 18 { 19 memset(g,0,sizeof(g)); 20 cin>>n>>e; 21 for(i=1;i<=e;++i) 22 { 23 scanf("%d%d",&x,&y); 24 g[x][y]=g[y][x]=1; 25 du[x]++;du[y]++; 26 } 27 start=1; 28 for(i=1;i<=n;++i) 29 if(du[i]%2==1) 30 start=i; 31 circuitpos=0; 32 find_circuit(start); 33 for(i=1;i<=circuitpos;++i) 34 printf("%d ",circuit[i]); 35 }