AtCoder ABC 168 D - .. (Double Dots) (緑色, 400 点)

BFS 木とか、BFS による経路復元とか、その辺りの理解を問いかける教育的問題だった！！！

問題へのリンク

問題概要

頂点、 辺の無向グラフが与えられる。頂点 1 以外のすべての頂点に対し「みちしるべとなる頂点」を、以下の条件を満たすように設定することが可能かどうかを判定し、可能ならば一例を示せ。

• 頂点 1 以外の任意の頂点 v に対し、その頂点から「みちしるべとなる頂点」を順に進むと、理論最短で頂点 1 にたどり着く

制約

• 
• 
• グラフは連結

考えたこと

問いかけがトリッキーだけど、グラフが連結である限り、かならず Yes になる！この問題は、シンプルに BFS 木というものについての理解があれば解ける問題とも言えそう。

BFS はそもそも始点 s から各頂点 v への最短路を求めるアルゴリズムと言える。で、普段 BFS するときは、各頂点 v への最短路の「長さ」だけを求めるイメージだけど、具体的な最短路そのものを求めたいという話もある。その手の話は以下の記事にまとめた。

qiita.com

さて、BFS の場合、最短路を復元する様子を図示すると、木として表現できることが知られている。具体的には、

• prev[ v ] := 始点 s から頂点 v への最短路において、v の手前の頂点

というものを、BFS しながら求めることができる。そして、

• prev[ v ] が、頂点 v の親

という風にすることで、いい感じに木になるのだ。これを BFS 木と呼ぶ (下図のような感じ)。

BFS 木がわかっていれば、今回の問題は解けたも同然。各頂点 v に対して、prev[ v ] を出力すれば OK！計算量は 。

#include <bits/stdc++.h>
using namespace std;
using Graph = vector<vector<int> >;
int N, M;
Graph G;

void solve() {
    vector<int> dist(N, -1);
    vector<int> prev(N, -1);
    queue<int> que;
    que.push(0);
    dist[0] = 0;
    while (!que.empty()) {
        int v = que.front();
        que.pop();
        for (auto nv : G[v]) {
            if (dist[nv] == -1) {
                dist[nv] = dist[v] + 1;
                prev[nv] = v;
                que.push(nv);
            }
        }
    }
    cout << "Yes" << endl;
    for (int i = 1; i < N; ++i) cout << prev[i] + 1 << endl;
}

int main() {
    cin >> N >> M;
    G.assign(N, vector<int>());
    for (int i = 0; i < M; ++i) {
        int a, b;
        cin >> a >> b;
        --a, --b;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    solve();
}