問題
$N$ 頂点 $M$ 辺の連結重み付き無向グラフの MST の重みを求めよ。$M \le 10^7$ なので $O(M \log N)$ で。
制約
$2 \le N \le 2 \times 10^5$
$N-1 \le M \le 10^7$
$1 \le w_i \le 10^9$
入出力例
入力例 1
4 5
1 2 3
1 3 1
2 3 4
2 4 2
3 4 5出力例 1
6ヒント (段階的開示)
ヒント1: 方向性
各コンポーネントの最小出辺を線形スキャンで見つけ、Union-Find で統合。これを $O(\log N)$ ラウンド。
ヒント2: アプローチ
1 ラウンドで連結成分数が必ず半分以下になる。全体 $O(M \log N)$。ソート不要。
ヒント3: 実装
cheapest[comp] を毎ラウンド初期化。
find() で常に最新 root を取得。模範解答 (Python)
import sys
from sys import stdin
def solve():
input = stdin.buffer.read().split()
idx = 0
N, M = int(input[idx]), int(input[idx+1]); idx += 2
edges = []
for _ in range(M):
u, v, w = int(input[idx]), int(input[idx+1]), int(input[idx+2])
idx += 3
edges.append((w, u - 1, v - 1))
parent = list(range(N))
rank = [0] * N
def find(x):
root = x
while parent[root] != root:
root = parent[root]
while parent[x] != root:
parent[x], x = root, parent[x]
return root
def union(x, y):
px, py = find(x), find(y)
if px == py:
return False
if rank[px] < rank[py]:
px, py = py, px
parent[py] = px
if rank[px] == rank[py]:
rank[px] += 1
return True
total = 0
num_comp = N
while num_comp > 1:
cheapest = [-1] * N
for i, (w, u, v) in enumerate(edges):
pu, pv = find(u), find(v)
if pu == pv: continue
if cheapest[pu] == -1 or edges[cheapest[pu]][0] > w:
cheapest[pu] = i
if cheapest[pv] == -1 or edges[cheapest[pv]][0] > w:
cheapest[pv] = i
added = False
for comp in range(N):
if cheapest[comp] == -1: continue
if find(comp) != comp: continue
w, u, v = edges[cheapest[comp]]
if union(u, v):
total += w
num_comp -= 1
added = True
if not added:
break
print(total)
solve()Step-by-Step 解説
1Kruskal vs Borůvka
$M \gg N \log N$ ならソート不要な Borůvka が最速。
$M \gg N \log N$ ならソート不要な Borůvka が最速。
2ラウンド数
各ラウンドで連結成分数が半分以下に。$O(\log N)$ ラウンド。
各ラウンドで連結成分数が半分以下に。$O(\log N)$ ラウンド。
3Union-Find
find() で最新 root を取得し、cheapest を更新。4実装注意
union() の戻り値で二重追加を防止。5Karger-Klein-Tarjan
Borůvka + Random Contraction で期待 $O(M)$。
Borůvka + Random Contraction で期待 $O(M)$。
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| cheapest を頂点で管理 | 古い root 参照 | find() で最新 root |
| ラウンド後リセット忘れ | 前ラウンドの値が残る | cheapest = [-1]*N 毎回 |
| 自己ループ処理漏れ | 同コンポーネント辺 | if pu == pv: continue |
次のステップ
- 動的 MST（辺追加・削除）+ LCT