题目描述

如果一个连通图存在一笔画经过所有边，则一笔画的路径叫做欧拉路，如果最后又回到起点，那这个路径叫做欧拉回路。

根据一笔画的两个定理，如果寻找欧拉回路，对任意一个点执行深度优先遍历；找欧拉路，则对一个奇点执行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

数据范围与提示

m<=1005 本题为无向图

欧拉回路定理

1.无向图：如果一个无向图是连通的，且最多只有两个奇点，则一定存在欧拉回路。如果有两个奇点，则必须从其中一个奇点出发，另一个奇点终止；如果奇点不存在，则可以从任意点出发，最终一定会回到该点(成为欧拉回路)

2.有向图：最多只能够有两个点的入度不等于出度，而且必须是其中一个点的出度恰好比入度大1(把它作为起点)，另一个的入度比出度大1(把它作为终点)。

我的代码(60pts)

#include<bits/stdc++.h>
#define in scanf
#define out printf
#define pre(i,a,b) for(int i=(a);i<=(b);i++)
#define bre(i,a,b) for(int i=(a);i>=(b);i--)
#define gre(i,a) for(auto i:a)
#define wl while
#define aya long long
#define x1 xxxsssxxx
#define x0 xxxxsxxxx
#define y1 yyysssyyy
#define y0 yyyysyyyy
#define clean(a) wl(!a.empty()){a.pop();}
#define inf 0x3f3f3f3f
#define lnf 0x3f3f3f3f3f3f3f3f
#define fi first
#define se second
using namespace std;
int n,m,flag=0,head=-1,tail=-1,vis[1005][1005];
vector<int> g[1005];
void dfs(int u){
	out("%d ",u);
	gre(v,g[u]){
		if(!vis[u][v]){
			vis[u][v]=1;
			vis[v][u]=1;
			dfs(v);
		}
	}
}
void solve(){
	in("%d%d",&n,&m);
	pre(i,1,m){
		int u,v;
		in("%d%d",&u,&v);
		g[u].push_back(v);
		g[v].push_back(u);
	}
	pre(i,1,n){
		sort(g[i].begin(),g[i].end());
	}
	pre(i,1,n){
		if(g[i].size()%2==1){
			if(head==-1){
				head=i;
				flag=1;
			}else{
				tail=i;
				if(g[i].size()<g[head].size()){
					swap(head,tail);
				}
			}
		}
	}
	if(flag){
		dfs(head);
	}else{
		dfs(1);
	}
	return;
}
int main(){
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	int t=1;
	//in("%d",&t);
	pre(i,1,t){
		solve();
	}
	return 0;
}