Day 143-Q3 | ボルーフカ法

問題

$N$頂点$M$辺の連結な無向グラフ（正の辺重み）が与えられる。最小全域木（MST）の総重みをボルーフカ法で求めよ。

ボルーフカ法の手順

各頂点を1つの連結成分として初期化
成分数が1になるまで以下を繰り返す（1回=1フェーズ）：各成分から出る最小コスト辺を1本選び、選ばれた辺を（重複除き）すべてMSTに追加し成分を併合
MSTに追加された辺の重みの総和を出力

各フェーズで成分数は必ず半分以下になるため$O(\log N)$フェーズ、全体$O(M\log N)$で計算する。

入力形式

N M
u_1 v_1 w_1
:
u_M v_M w_M

制約

$2 \le N \le 2\times10^5$

$N-1 \le M \le 2\times10^5$

グラフは連結

$1 \le w_i \le 10^9$

入出力例

入力例1

出力例1

フェーズ1で1-2(重み1)と3-4(重み1)を選択、フェーズ2で2-3(重み2)を選択。合計1+1+2=4。

概念図：フェーズごとの並列併合

ヒント（段階的開示）

ヒント1（方向性）

「各成分が最小コストの隣接辺を選ぶ」操作を1回行うと、選ばれた辺は必ずMSTに含まれる（カット性質の一般化）。これを全成分について同時に行い、複数の成分をまとめて併合することで、Kruskal/Primより1ステップで進む量が大きくなる。

ヒント2（アプローチ）

各フェーズで全辺を1回スキャンし、両端点の根が異なるなら両方の根の「最小外向き辺」記録を更新する。スキャン後に記録された辺を実際にUnionし、成功した場合のみMST総重みに加算する。各成分は必ず最低1回併合されるためフェーズ数は$O(\log N)$。

ヒント3（誘導）

def boruvka(N, edges):
    parent = list(range(N))
    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x
    def union(x, y):
        rx, ry = find(x), find(y)
        if rx == ry:
            return False
        parent[rx] = ry
        return True

    total = 0
    num_components = N
    while num_components > 1:
        cheapest = [-1] * N
        for i, (u, v, w) in enumerate(edges):
            ru, rv = find(u), find(v)
            if ru == rv:
                continue
            if cheapest[ru] == -1 or edges[cheapest[ru]][2] > w:
                cheapest[ru] = i
            if cheapest[rv] == -1 or edges[cheapest[rv]][2] > w:
                cheapest[rv] = i
        for root in range(N):
            i = cheapest[root]
            if i == -1:
                continue
            u, v, w = edges[i]
            if union(u, v):
                total += w
                num_components -= 1
    return total

模範解答 (Python)

import sys

def main():
    data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(data[idx]); idx += 1
    M = int(data[idx]); idx += 1

    edges = []
    for _ in range(M):
        u = int(data[idx]) - 1; idx += 1
        v = int(data[idx]) - 1; idx += 1
        w = int(data[idx]); idx += 1
        edges.append((u, v, w))

    parent = list(range(N))

    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    def union(x, y):
        rx, ry = find(x), find(y)
        if rx == ry:
            return False
        parent[rx] = ry
        return True

    total = 0
    num_components = N
    while num_components > 1:
        cheapest = [-1] * N
        for i, (u, v, w) in enumerate(edges):
            ru, rv = find(u), find(v)
            if ru == rv:
                continue
            if cheapest[ru] == -1 or edges[cheapest[ru]][2] > w:
                cheapest[ru] = i
            if cheapest[rv] == -1 or edges[cheapest[rv]][2] > w:
                cheapest[rv] = i
        merged_any = False
        for root in range(N):
            i = cheapest[root]
            if i == -1:
                continue
            u, v, w = edges[i]
            if union(u, v):
                total += w
                num_components -= 1
                merged_any = True
        if not merged_any:
            break

    print(total)

main()

Step-by-Step 解説

1成分から出る最小辺は必ずMSTに含まれる
任意の頂点部分集合を跨ぐ辺のうち最小重みの辺は必ずどれかのMSTに含まれる（カット性質）。

21フェーズで成分数が半分以下になる理由
各成分は必ず最低1本選んで併合されるため、ペアリングの性質上フェーズ後の成分数は半分以下になる。

3フェーズ数と計算量
成分数が毎回半分以下になるため最大$O(\log N)$フェーズ、各フェーズ$O(M)$で全体$O(M\log N)$。

4Kruskal/Primとの違い
Kruskalは辺を逐次的にソート順で処理、Primは1成分を優先度付きキューで拡張。ボルーフカは複数成分が同時並行に成長し並列/分散処理に向く。

5重複選択の実装上の注意
同じ辺が両端の成分双方から選ばれることがあるため、unionが実際に成功した場合のみ加算する。

よくあるミス

ミス	原因	正しい書き方
同じ辺が両側から選ばれて重みを2回加算	unionの戻り値を見ずに常に加算	union(u,v)がTrueのときのみ加算する
辺スキャン中に逐次Unionしてしまう	スキャン中に成分が変化し「同時並列選択」の前提が崩れる	スキャン中はUnionせずフェーズ最後にまとめてUnion
フェーズ数をN回程度と誤解する	成分数が半分以下になる収束の速さを理解していない	成分数は各フェーズで最大でも半分になりO(log N)フェーズで済む
非連結グラフで無限ループ	成分が併合されなくなってもwhileが回り続ける	1フェーズで併合が0件ならbreakする安全策を入れる
cheapest[root]の初期値を0にしてしまう	未発見状態と辺0が最小の状態を区別できない	初期値は-1（未発見）にする

次のステップ

発展: 辺集合が陽に与えられない平面上の点集合（全点対ユークリッド距離が暗黙のグラフ）に対し、最小外向き辺探索をk-d木で高速化する手法を調べよ。
発展2: 各フェーズの最小辺探索を独立プロセスに割り当てた場合の理論的並列計算量O(log N)ラウンドを実際に体感してみよ。

自己評価

完全理解おおむね理解要復習

Day 143-Q3 — ボルーフカ法（Borůvka's Algorithm）による最小全域木

問題