[ABC213D] Takahashi Tour 题解

题目传送门

一道 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;
}