AcWing366 看牛

题面

给定 $N$个点 $M$条边的无向图，求一条路径，从节点 $1$ 出发，最后回到节点 $1$，并且满足每条边恰好被沿着正、反两个方向分别经过一次。

若有多种方案，输出任意一种即可。

输入格式

第一行包含两个整数 $N$ 和 $M$。

接下来 $M$ 行每行包含两个整数 $a$ 和 $b$，表示点 $a$ 和点 $b$ 之间存在一条边。

输出格式

共 $2M+1$ 行，每行包含一个整数，共同描述出了满足条件的一条路径。

数据范围

$1≤N≤10^4$
$1≤M≤5\times{10^4}$

输入样例：

4 5
1 2
1 4
2 3
2 4
3 4

输出样例：

1
2
3
4
2
1
4
3
2
4
1

思路

虽然说是无向图，但是可以把它看成是双向边的有向图，这样就可以在这张有向图跑一遍欧拉回路了，因为它满足有向图欧拉回路的条件：每个点入度=出度。

因为我们把一条边拆成了两条边，所以记得边开两倍空间。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+7,M=5e4+7;
int n,m;
int ans[M<<1];
struct edge
{
    int to,nxt;
}e[M<<1];
stack<int> S;
int fir[N],cnt;
void add(int u,int v)
{
    e[++cnt].nxt=fir[u];
    e[cnt].to=v;
    fir[u]=cnt;
}
void ola(int x)
{
    for(int i=fir[x];i;i=fir[x])
    {
        int v=e[i].to;
        fir[x]=e[i].nxt;
        ola(v);
    }
    S.push(x);
}
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);
    }
    ola(1);
    int p=0;
    while(!S.empty())
    {
        int a=S.top();
        S.pop();
        ans[++p]=a;
    }
    // reverse(ans+1,ans+1+p);
    for(int i=1;i<=p;i++)
        printf("%d\n",ans[i]);
    return 0;
}