欧拉路径与Hierholzer算法

欧拉路径：如果图G中的一个路径包括每个边恰好一次，则该路径称为欧拉路径(Euler path)。

欧拉回路：如果一个回路是欧拉路径，则称为欧拉回路(Euler circuit)。
具有欧拉回路的图称为欧拉图（简称E图）。具有欧拉路径但不具有欧拉回路的图称为半欧拉图。

欧拉路径存在的条件：

1. 图为无向连通图
2. 奇数点为2个或0个，其余点度数为偶数(两个奇数点即为起点和终点)。

证明：
我们要使每个边恰好经过一次，那么对于每个中间点，必然从一条入边到达这个点再从一条出边离开这个点那么入边数必然等与出边数，换句话说只要到达一个点必然要有一条边离开这个点。

1.当奇数点个数大于2时，必然有不能完全遍历每一条边。
2.当奇数点为0个时，说明每个点都能成功到达并离开，那此图就构成了欧拉回路，我们必然可以从一个点出发最后再回到这个点。

Hierholzer算法

我们记录每个点的度数，以便于找到起点和终点，当奇数点为2时，选择其中一个点作为起点，另一个点为终点，当奇数点为0时，随机找一个点作为起点，此时图构成欧拉回路，当奇数点不为0或2时，欧拉路不存在。
我们使用DFS遍历每一条边，每走过一条边，就将他删去，保证每条边只经过一次。
我们使用栈来存储路径，以便于最后倒序输出。

#include<bits/stdc++.h>
using namespace std;
const int N=550;

int n;
int g[N][N];
int deg[N];

int odd[N];
int even[N];
int cnt;
stack<int>st;
int maxn;

void Hierholzer(int x)
{
	for(int i=1;i<=maxn;i++)
	{
		if(g[x][i])
		{
			g[x][i]--;
			g[i][x]--;
			Hierholzer(i);
		}
	}
	st.push(x);
}

int main(){
	
	cin>>n;
	int c=550;
	for(int i=1;i<=n;i++)
	{
		int x,y;
		cin>>x>>y;
		g[x][y]++;
		g[y][x]++;
		c=min(c,x);
		c=min(c,y);
		deg[x]++;
		deg[y]++;
		maxn=max(maxn,max(x,y));
	}
	
	for(int i=1;i<=maxn;i++)
	{
		if(deg[i]&1) odd[++cnt]=i;
	}
	if(cnt!=2&&cnt)
	{
		printf("No solution!");
		return 0;
	}
	int start;
	if(cnt) start=min(odd[1],odd[2]);
	else start=c;
	
	Hierholzer(start);
	
	while(st.size())
	{
		printf("%d\n",st.top());
		st.pop();
	}
	
	return 0;
}