一道 dfs 序题。
题目中高桥每次只会去最小的那个点，所以要先对整张图进行排序。
for (int i = 1; i <= n; i++) sort(g[i].begin(), g[i].end());
然后考虑 dfs。高桥不会走重复的点，所以我们可以开一个 vis 数组进行标记。然后我们需要处理高桥君如果无路可走会返回上一个点的情况。在 dfs 回溯后输出当前节点即可。
void dfs(int cur) {
vis[cur] = 1;
cout << cur << " ";
for (auto v : g[cur]) {
if (vis[v]) continue;
dfs(v);
cout << cur << " ";
}
}
Code
#include <bits/stdc++.h>
#define ll long long
#define INF 1e9
using namespace std;
vector <int> g[200005];
bool vis[200005]; // 标记高桥走过的点
int n;
void dfs(int cur) {
vis[cur] = 1; // 每走过一个点就标记一下
cout << cur << " ";
for (auto v : g[cur]) {
if (vis[v]) continue; // 如果已经走过了就不走了
dfs(v); // 注意这里要先 dfs
cout << cur << " ";
}
}
signed main() {
ios :: sync_with_stdio(0);
cin >> n;
for (int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
for (int i = 1; i <= n; i++) sort(g[i].begin(), g[i].end()); // 排序
dfs(1);
return 0;
}