Day 007-Q2 | 最小全域木 Kruskal

問題

$N$ 頂点 $M$ 辺の重み付き無向グラフが与えられる。最小全域木（MST）のコスト（辺の重みの総和）を求めよ。グラフが連結でない場合は -1。

制約

$2 \le N \le 10^5$

$1 \le M \le 3\times10^5$

$1 \le u_i, v_i \le N$

$1 \le w_i \le 10^9$

入出力例

入力例 1

出力例 1

入力例 2

3 1
1 2 5

出力例 2

-1

ヒント (段階的開示)

ヒント1: 方向性

辺を重みの小さい順に貪欲に選ぶ。

ヒント2: アプローチ

閉路を作らないように辺を選ぶには Union-Find を使う。

ヒント3: 誘導

edges.sort(key=lambda x: x[2])
for u, v, w in edges:
    if find(u) != find(v):
        union(u, v)
        total += w
        count += 1
if count == N - 1: print(total)
else: print(-1)

模範解答 (Python)

import sys
input = sys.stdin.readline

def main():
    N, M = map(int, input().split())
    edges = []
    for _ in range(M):
        u, v, w = map(int, input().split())
        edges.append((w, u-1, v-1))

    parent = list(range(N))
    rank = [0] * 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
        if rank[rx] < rank[ry]:
            rx, ry = ry, rx
        parent[ry] = rx
        if rank[rx] == rank[ry]:
            rank[rx] += 1
        return True

    edges.sort()
    total = 0
    count = 0
    for w, u, v in edges:
        if union(u, v):
            total += w
            count += 1
            if count == N - 1:
                break

    print(total if count == N - 1 else -1)

main()

Step-by-Step 解説

1Kruskal のアイデア
「最も軽い辺から順に選ぶ。ただし閉路を作る辺はスキップ」。カット性質で正当性が保証される。

2閉路判定に Union-Find
find(u) == find(v) なら閉路 → スキップ。

3N-1 本選べたか確認
全域木はちょうど $N-1$ 本の辺を持つ。

4計算量
ソート $O(M \log M)$ + Union-Find $O(\alpha(N))$ ≈ $O(M \log M)$。

よくあるミス

ミス	原因	正しい書き方
連結チェックを忘れる	MST が存在しない場合を考慮しない	`count == N-1` で判定
辺の向きを重みと混同	タプルの順序ミス	`(w, u, v)` でソートキーを重みに
Union-Find の経路圧縮なし	TLE	`parent[x] = parent[parent[x]]` を使う

Day 007-Q2 — 最小全域木 Kruskal

問題

制約