\(P6066\) \(Watchcow\) \(S\)
一、题目描述
\(Farmer\) \(John\)有\(N\)个农场（\(2 ≤ N ≤ 10^4\)），这些农场由\(M\)条道路连接（\(1 \leq M \leq 5 \times 10^4\)）。不保证没有重边。\(Bassie\)从\(1\)号农场开始巡逻，每条路必须从两个方向各走恰好一遍，最后回到\(1\)号农场。
请输出一条满足上述要求的路径。
保证这样的路径存在。如果有多条路径，任意输出一条即可。
输入格式：
第一行两个整数\(N , M\)。
接下来\(M\)行，每行两个整数\(u , v\)，描述一条\(u\)到\(v\)的道路。
输出格式：
输出经过的农场，一行一个。
二、解题思路
这是欧拉回路问题，可以用\(DFS\)解决。参考https://blog.csdn.net/qq_46105170/article/details/115060171。
三、实现代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 10, M = 1e5 + 10;
int n, m;
// 链式前向星
int e[M], h[N], idx, w[M], ne[M];
void add(int a, int b, int c = 0) {
e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}
// 无向图欧拉回路
void dfs(int u) {
for (int i = h[u]; ~i; i = h[u]) {
h[u] = ne[i];
dfs(e[i]);
}
// 记录点
printf("%d\n", u);
}
int main() {
memset(h, -1, sizeof h);
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(1);
return 0;
}