题目描述
给定N个点M条边的无向图,求一条路径,从节点1出发,最后回到节点1,并且满足每条边恰好被沿着正、反两个方向分别经过一次。
若有多种方案,输出任意一种即可。
输入格式
第一行包含两个整数N和M。
接下来M行每行包含两个整数a和b,表示点a和点b之间存在一条边。
输出格式
共2M+1行,每行包含一个整数,共同描述除了满足条件的一条路径。
数据范围
1≤N≤104,
1≤M≤5∗104
样例
输入样例:
4 5
1 2
1 4
2 3
2 4
3 4
输出样例:
1
2
3
4
2
1
4
3
2
4
1
算法1
(欧拉回路) $O(m)$
一般的求欧拉回路的模板会把一条无向边的两条分解边都进行标记,本题要求满足每条边恰好被沿着正、反两个方向分别经过一次。所以每次遍历的时候只把当前的边进行标记即可。
时间复杂度
参考文献
C++ 代码
#include <iostream>
using namespace std;
const int N=100100,M=500050;
int e[M*2],ne[M*2],h[N];
int stack[1000010],ans[1000010];
bool vis[N];
int n,m,idx,t,top;
void add(int a,int b)
{
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void euler()
{
stack[++top]=1;
while(top>0)
{
int x=stack[top],i=h[x];
while(i&&vis[i]) i=ne[i];
if(i)
{
stack[++top]=e[i];
vis[i]=true;//一般的模板这里是 vis[i]=vis[i^1]=true;
h[x]=ne[i];
}
else
{
top--;
ans[++t]=x;
}
}
}
int main()
{
cin>>n>>m;
idx=2;
for(int i=1;i<=m;i++)
{
int a,b;
scanf("%d%d",&a,&b);
add(a,b);add(b,a);
}
euler();
for(int i=t;i;i--)
printf("%d\n",ans[i]);
return 0;
}