「POJ2230」Watchcow

题意：一个 $n$ 个点 $m$ 条边的无向图，要求从 $1$ 号节点出发，刚好把所有边正反都走一遍再回到 $1$ 号节点，输出一个满足条件的路径方案。

一个非常典型的欧拉回路问题。

欧拉路是怎么回事呢？我们用 dfs ，判断每条边有没有被访问过，如果没有就打上标记，继续深搜，同时把这个边到达的点入栈，最后倒序输出栈中的所有节点便是一个欧拉回路。

这种算法的时间复杂度为 O(nm)，因为一个点会被重复访问多次。我们可以采用邻接表存图，每次访问边后就修改表头 $head[u]$，让它指向下一条边，就跳过了被访问的所有边。

同时我们可以把递归转化为非递归，手写递归栈来解决问题。这样就避免了系统栈的溢出。

最后优化后的时间复杂度为 O(n+m)，同时在这道题中，正好要求把所有边正反访问一次，那我们直接把标记去掉都行了，因为本来存图时也是正反各存一次，这时只用修改表头的放大刚好满足题意。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
int n,m,top,num;
int stack[100101],ans[500101];
int head[100101],cnt;
struct node
{
	int next;
	int to;
}e[201010];
void add(int from,int to)
{
	e[++cnt].next=head[from];
	e[cnt].to=to;
	head[from]=cnt;
}
void dfs()
{
	stack[++top]=1;
	while(top>0)
	{
		int u=stack[top];
		int i=head[u];
		if(i)
		{
			stack[++top]=e[i].to;
			head[u]=e[i].next;
		}
		else
		{
			top--;
			ans[++num]=u;
		}
	}
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		int a,b;
		scanf("%d%d",&a,&b);
		add(a,b);
		add(b,a);
	}
	dfs();
	for(int i=num;i;i--)
		printf("%d\n",ans[i]);
	return 0;
}