【C++解説】すべての道が首都（都市0）へつながるよう経路を並べ替える最小コストの求め方

問題概要

0 から n-1 までの番号が振られた n 個の都市があるとします。さらに、n-1 本の道路が存在し、任意の2つの都市間を移動する経路はただ一つしかありません。交通省は道路が非常に狭いため、すべての道路を一方向のみ通行可能とする一方通行化を決定しました。

道路は配列 connections で表現され、connections[i] = [a, b] は「都市 a から 都市 b へ向かう一方向の道路」を意味します。

ここで、首都（都市 0）で大規模なイベントが開催され、多くの人々が首都を目指して移動することになりました。そこで、すべての都市から都市 0 に到達できるように、一部の道路の向きを変更する必要があります。このとき、向きを変更しなければならない道路の最小本数を求めてください。

入力例

n = 6、connections = [[0,1],[1,3],[2,3],[4,0],[4,5]] の場合：

この場合の出力は 3 となります。図の赤で示した3本の道路の向きを変更することで、すべての都市から首都へ到達できるようになるためです。

解法のアプローチ

この問題は、BFS（幅優先探索）を用いて効率的に解くことができます。考え方は以下の通りです。

• 元の向きの道路を記録するリスト graph1 と、逆向きの道路を記録するリスト graph2 を、サイズ N = 5×10^4 + 5 の配列として定義します。
• 各道路 [a, b] に対して、graph1[a] に b を追加し、graph2[b] に a を追加します。
• 首都（都市 0）から BFS を開始します。
  • graph2（逆向きの辺）でたどれる都市は、既に首都へ向かう道が開通しているため、コスト 0 で到達可能です。
  • graph1（元の向きの辺）でたどれる都市は、その道路の向きを変更する必要があるため、コスト 1 を加算します。
• 訪問済みの都市を set で管理し、同じ都市を二重に処理しないようにします。
• 最終的に、各都市に到達する際にかかったコストの合計が答えとなります。

C++による実装例

以下の実装を見ると、理解がより深まるでしょう。

#include <bits/stdc++.h>
using namespace std;
const int N = 5e4 + 5;
class Solution {
public:
    vector<int> graph1[N];
    vector<int> graph2[N];
    int minReorder(int n, vector<vector<int> >& e){
        map<int, int> in;
        for (auto& it : e) {
            graph1[it[0]].push_back(it[1]);
            graph2[it[1]].push_back(it[0]);
        }
        vector<int> dist(n, N + 10);
        int ret = 0;
        in[0] = 0;
        dist[0] = 0;
        queue<int> q;
        q.push(0);
        set<int> visited;
        visited.insert(0);
        while (!q.empty()) {
            int node = q.front();
            q.pop();
            ret += dist[node];
            for (auto& it : graph2[node]) {
                if (!visited.count(it) && dist[it] > 0) {
                    dist[it] = 0;
                    q.push(it);
                    visited.insert(it);
                }
            }
            for (auto& it : graph1[node]) {
                if (!visited.count(it) && dist[it] > 1) {
                    dist[it] = 1;
                    q.push(it);
                    visited.insert(it);
                }
            }
        }
        return ret;
    }
};
main(){
    Solution ob;
    vector<vector<int>> v = {{0,1},{1,3},{2,3},{4,0},{4,5}};
    cout << (ob.minReorder(6,v));
}

入力

6,{{0,1},{1,3},{2,3},{4,0},{4,5}}

出力

3

まとめ

木構造のグラフにおいて、すべての都市から首都へ到達できるようにするには、BFS で首都から外側へ探索し、「元の向きの道路を使って首都から遠ざかる方向へ進む場合」にのみコスト 1 をカウントするのがポイントです。この手法により、O(n) の計算量で最小の変更本数を求めることができます。