【ABC213】 D - Takahashi Tour

atcoder.jp

解法

木上のDFSを理解していますか？って感じの問題。

訪れていない都市を優先的に移動を繰り返すということで、深さ優先探索と同じ方法であることがわかる。
訪れていない都市がない時、元の都市に戻るという動作もDFSそのままだ。
いまいる都市が1なら処理を終了するというのが気になるかもしれないが、DFSでは必ず探索を開始した地点に戻ってくるため、実装において場合分けは必要としない。

今回は、初めて訪れた順番がいつか？だけでなく、元の都市に戻ったのはいつか？という情報も必要になる。
DFSでは、ノードに入った時間、出た時間が重要になることがある。
具体的には、どの行がどのタイミングで実行されるかを把握する必要があるということだ。

下はDFSの実装例だが、都市を訪れた時、出るときに適切に都市の番号を記録していけばよい。

void dfs(int n, int p, vector<vector<ll>> &G) { // n: 現在のノード, p: 親ノード, G: グラフ
    // ここは都市を訪れたときに実行される    

    for (auto a : G[n]) {
        if (a != p) { // 親への逆流防止
           dfs(a, n, G);
       }
    }

　// ここは都市を出る時に実行される
}

本番での実装

コンテスト中は与えられているグラフが木であることに気づいていなかったので、既に探索したかどうかのフラグを管理するseenという配列を使って実装しているが、木上のDFSでは親への逆流さえ防げれば良いので、これは必要なかったりする。
上の実装例と少し違うが、やっていることは同じ。

vector<ll> ans;
void dfs(int n, vector<vector<ll>> &G, vector<bool> &seen) {
    ans.push_back(n);

    for (auto a : G[n]) {
        if (!seen[a]) {
            seen[a] = 1;
            dfs(a, G, seen);
            ans.push_back(n);
        }
    }
}

void solve(long long N, std::vector<long long> A, std::vector<long long> B) {
    vector<vector<ll>> G(N+10);
    REP (i, N-1) {
        G[A[i]-1].push_back(B[i]-1);
        G[B[i]-1].push_back(A[i]-1);
    }

    REP (i, N) {
        ALL(sort, G[i]);
    }

    vector<bool> seen(N+10, false);
    seen[0] = 1;
    dfs(0, G, seen);
    
    REP (i, ans.size()) cout << ans[i]+1 << " ";
    cout << endl;
}