Takahashi Tour [AtCoder Beginner Contest 213 D]

https://atcoder.jp/contests/abc213/tasks/abc213_d

前提知識

• dfs

解説

https://atcoder.jp/contests/abc213/submissions/24895917

今回の問題はDFSというか、オイラーツアーというかという問題。
とにかく木上での深さ優先探索ができるなら解ける問題。

何から始めるのか

正直この問題を見たときにオイラーツアーが思い浮かんだので、そこから考えると解けた。
オイラーツアーについて勉強している人にとっては思いつきやすかったかもしれない。

だが、ルールに従ってシミュレーションをしてみると、移動の軌跡がちょうど木上でのDFSと同じ挙動になっているので、
とりあえずDFSでやってやればよさそうと感じ取れるかもしれない。

今回の問題の解法はただシミュレーションするだけである。

シミュレーション

木上のDFSをするときに隣接グラフを持つと思うが、その隣接グラフの各配列（遷移先をまとめた配列）は昇順ソートしておこう。
これは、ルールに含まれる「いまいる都市と道路で直接つながっている都市のうち、まだ訪れたことがない都市が存在するとき、
そのような都市のうち番号が最も小さい都市へ移動する」を満たすためである。
さて、まず都市1からスタートするので、dfsのスタート地点もそこから始める。
そこから遷移を始めていくが、どれもまだ訪れていない都市なので、遷移先で最小のもの（昇順ソートしているので最初のもの）を選んで移動する。
移動したら、都市番号を出力しておく。
で、遷移後にまた移動していくが、都市1から来ていて、そこはすでに訪れているので、先にそれ以外の頂点を訪れる必要がある。
で、全部訪れたら遷移元に戻っていく。
これはまさしくDFSの操作である。

なので、遷移先を昇順ソートしていけば、後はDFSをすれば勝手にルールを満たす動きになる。
後は、適切に都市番号の出力を行っていけば答えが構築できる。

int N;
vector<int> E[201010];
//---------------------------------------------------------------------------------------------------
void dfs(int cu, int pa = -1) {
    if (cu != 0) printf(" ");
    printf("%d", cu + 1);

    fore(to, E[cu]) if (to != pa) {
        dfs(to, cu);
        printf(" %d", cu + 1);
    }
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N - 1) {
        int a, b; cin >> a >> b;
        a--; b--;
        E[a].push_back(b);
        E[b].push_back(a);
    }
    rep(i, 0, N) sort(all(E[i]));
    
    dfs(0);
    printf("\n");
}