【题目描述】 如果一个图存在一笔画，则一笔画的路径叫做欧拉路，如果最后又回到起点，那这个路径叫做欧拉回路。
根据一笔画的两个定理，如果寻找欧拉回路，对任意一个点执行深度优先遍历；找欧拉路，则对一个奇点执行dfs，时间复杂度为O(m+n)，m为边数，n是点数。
【输入】 第一行n，m，有n个点，m条边，以下m行描述每条边连接的两点。
【输出】 欧拉路或欧拉回路,输出一条路径即可。
【输入样例】
5 5 1 2 2 3 3 4 4 5 5 1【输出样例】
1 5 4 3 2 1 #include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<string> #include<cstdlib> #include<queue> #include<vector> #include<set> #define INF 0x3f3f3f3f #define PI acos(-1.0) #define N 501 #define MOD 123 #define E 1e-6 using namespace std; int n,m; int g[N][N]; int dis[N],path[N*2]; int cnt; void dfs(int i) { for(int j=1;j<=n;j++) if(g[i][j]) { g[i][j]=0; g[j][i]=0; dfs(j); } path[cnt++]=i; } int main() { cin>>n>>m; for(int i=1;i<=m;i++) { int x,y; cin>>x>>y; g[x][y]=1; g[y][x]=1; dis[x]++; dis[y]++; } int start=1; for(int i=1;i<=n;i++) if(dis[i]%2) { start=i; } dfs(start); for(int i=cnt-1;i>=0;i--) cout<<path[i]<<" "; return 0; }