[USACO05JAN]Watchcow S(欧拉回路)

[USACO05JAN]Watchcow S

题目描述

Farmer John 有 $N$ 个农场（$2\le N\le 10^4$），这些农场由 $M$ 条道路连接（$1\le M\le 5\times 10^4$）。不保证没有重边。

Bassie 从 $1$ 号农场开始巡逻，每条路必须从两个方向各走恰好一遍，最后回到 $1$ 号农场。

请输出一条满足上述要求的路径。

保证这样的路径存在。如果有多条路径，任意输出一条即可。

输入格式

第一行两个整数 $N,M$。

接下来 $M$ 行，每行两个整数 $u,v$，描述一条 $u$ 到 $v$ 的道路。

输出格式

输出经过的农场，一行一个。

样例 #1

样例输入 #1

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

样例输出 #1

1
2
3
4
2
1
4
3
2
4
1

思路：

无向图转有向图 --> 跑有向图的欧拉回路

AC代码如下：

#include <bits/stdc++.h>
#define buff \ ios::sync_with_stdio(false); \ cin.tie(0);
//#define int long long
using namespace std;
const int N = 1e4 + 9, M = 1e5 + 9;
int n, m;
int e[M], h[M], ne[M], idx;
int s[M], cnt;
bool st[M];****
void add(int a, int b)
{
    
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}
void dfs(int x)
{
    
    for (int i = h[x]; ~i; i = ne[i])
    {
    
        if (!st[i])
        {
    
            st[i] = true;
            int j = e[i];
            dfs(j);
            s[++cnt] = j;
        }
    }
}
void solve()
{
    
    memset(h, -1, sizeof h);
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
    
        int u, v;
        cin >> u >> v;
        add(u, v);
        add(v, u);
    }
    dfs(1);
    s[++cnt] = 1;
    for (int i = cnt; i >= 1; i--)
        cout << s[i] << '\n';
}
int main()
{
    
    buff;
    solve();
}