AtCoder ABC 213 D - Takahashi Tour (茶色, 400 点)

DFS (深さ優先探索) の動きをシミュレーションする問題。

• 問題へのリンク

問題概要

頂点番号が であるような木が与えられます。

今このグラフにおいて、頂点 1 から出発して、次の動きを繰り返します。

• いまいる頂点に隣接する頂点のうち、まだ訪れたことがない頂点が存在するとき、そのような頂点のうち番号が最も小さいところへ移動する
• そのような頂点が存在しないとき
  • いまいる頂点が頂点 1 であるとき、終了する
  • そうでないとき、いまいる頂点を初めて訪れたときに直前にいた頂点へ移動する

このシミュレーションの過程で訪れる頂点の番号の過程を答えてください。

制約

• 

考えたこと

この問題のシミュレーションは、木において、頂点 1 を根として深さ優先探索を実施することを意味しています。

探索された順に頂点を出力すればよいでしょう。なお、この頂点順のことを特に Euler ツアーとよびます。今後さまざまな、より高度な問題で活躍するものとなっています。

計算量は となります。

コード

#include <bits/stdc++.h>
using namespace std;

// グラフ構造体
using Graph = vector<vector<int>>;

// DFS
void rec(const Graph &G, int v, int p = -1) {
    // 行きがけ順の頂点出力
    cout << v+1 << " ";

    for (int ch: G[v]) {
        // 親へは遡らない
        if (ch == p) continue;

        // 再帰的に
        rec(G, ch, v);

        // 戻ってきたらまた出力
        cout << v+1 << " ";
    }
}

int main() {
    // 入力
    int N;
    cin >> N;
    Graph G(N);
    for (int i = 0; i < N-1; ++i) {
        int a, b;
        cin >> a >> b;
        --a, --b;
        G[a].push_back(b);
        G[b].push_back(a);
    }

    // 各頂点の隣接頂点を番号が小さい順に
    for (int v = 0; v < N; ++v) {
        sort(G[v].begin(), G[v].end());
    }

    // DFS
    rec(G, 0);
    cout << endl;
}