AW366 看牛 （欧拉回路）

题目地址

---

简单分析：

• 由于每条边必须走两遍，等价于走完一条边后不删除反向边.

易错点：

• ans和stack数组应当开到MAXM.

---

#include<cstdio>
#include<iostream>
using namespace std;
const int MAXN=2e4,MAXM=1e5;
struct Edge{
	int from,to,w,nxt;
}e[MAXM];
int head[MAXN],edgeCnt=1;
void addEdge(int u,int v,int w){
	e[++edgeCnt].from=u;
	e[edgeCnt].to=v;
	e[edgeCnt].w=w;
	e[edgeCnt].nxt=head[u];
	head[u]=edgeCnt;
}
int ans[MAXM],ansCnt=0;//
int stck[MAXM],top=0;//
void euler(){
	stck[++top]=1;
	while(top){
		int x=stck[top];
		if(!head[x]){
			ans[++ansCnt]=x;
			top--;
		}else{
			stck[++top]=e[head[x]].to;
			head[x]=e[head[x]].nxt;
		}
	}
}
int main(){
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		int u,v;
		scanf("%d%d",&u,&v);
		addEdge(u,v,1);
		addEdge(v,u,1);
	}
	euler();
	for(int i=1;i<=ansCnt;i++)
		printf("%d
",ans[i]);
	return 0;
}