算法
(图上dfs、排序)
先对每个节点的子节点进行排序,然后在树上做一遍 dfs
即可
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::vector;
vector<vector<int>> to;
vector<int> ans;
void dfs(int v, int p = -1) {
ans.push_back(v);
for (int u : to[v]) {
if (u == p) continue;
dfs(u, v);
ans.push_back(v);
}
}
int main() {
int n;
cin >> n;
to.resize(n);
rep(i, n - 1) {
int a, b;
cin >> a >> b;
--a; --b;
to[a].push_back(b);
to[b].push_back(a);
}
rep(i, n) sort(to[i].begin(), to[i].end());
dfs(0);
for (int v : ans) cout << v + 1 << " ";
return 0;
}