Day 048-Q4 | Karger's Algorithm（乱択最小カット）

問題

$N$ 頂点 $M$ 辺の無向グラフが与えられる。グローバル最小カット（グラフを2つの非空部分に分ける辺集合の最小枚数）を求めよ。辺重みはすべて 1 とする。

制約

$2 \le N \le 500$

$1 \le M \le 2000$

連結グラフ（保証）

自己ループなし

時間制限: 3秒（乱択アルゴリズム使用）

入出力例

入力例 1

出力例 1

グラフは K4（完全グラフ）に近い形。辺 {(2,4),(3,4)} を切ると頂点4が孤立 → カット=2。最小カットは2。

概念図: Karger's Algorithm の縮約プロセス

ヒント（段階的開示）

ヒント1: 方向性

Karger's Algorithm は乱択アルゴリズムです。ランダムに辺を選んで縮約（contraction）を繰り返し、最終的に2頂点になったときの辺数が最小カットの候補です。多数回繰り返すことで高確率で正解を得ます。

ヒント2: アプローチ

1回の試行: ランダムな辺 $(u,v)$ を選び、$u$ と $v$ を合併（自己ループは削除、多重辺は保持）
N-2 回縮約後、残った2点間の辺数が最小カット候補
1回の試行で正解する確率 $\ge \frac{2}{N(N-1)}$
$O(N^2 \log N)$ 回繰り返すと失敗確率 $1/N$ 以下

ヒント3: 実装骨格（Union-Find ベース）

def karger_once(edges, N):
    parent = list(range(N+1))
    rank = [0] * (N+1)

    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

    components = N
    perm = list(range(len(edges)))
    random.shuffle(perm)
    for i in perm:
        if components == 2: break
        u, v = edges[i]
        if union(u, v): components -= 1

    return sum(1 for u, v in edges if find(u) != find(v))

模範解答 (Python)

import sys
import random
from math import log

def solve():
    data = sys.stdin.read().split()
    idx = 0
    N, M = int(data[idx]), int(data[idx+1]); idx += 2
    edges = []
    for _ in range(M):
        u, v = int(data[idx]), int(data[idx+1]); idx += 2
        edges.append((u, v))

    def karger_once():
        parent = list(range(N+1))
        rank = [0] * (N+1)

        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):
            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

        components = N
        perm = list(range(M))
        random.shuffle(perm)
        for i in perm:
            if components == 2:
                break
            u, v = edges[i]
            if union(u, v):
                components -= 1

        return sum(1 for u, v in edges if find(u) != find(v))

    # 試行回数: N^2 * ln(N) 回で高確率正解
    trials = max(50, min(500, int(N * N * log(N + 1)) // 4))

    ans = M
    for _ in range(trials):
        ans = min(ans, karger_once())

    print(ans)

solve()

Step-by-Step 解説

1縮約（Contraction）の仕組み
辺 $(u, v)$ を縮約すると $u$ と $v$ を1頂点に合併する。自己ループは削除するが多重辺は保持する。多重辺を保持することで最小カット辺が残りやすくなる。

2Union-Find で縮約を管理
辺リストをシャッフルし、順に処理。Union-Find で異なる成分間の辺のみ縮約（Union）。components が 2 になったら終了。残辺数（find(u) ≠ find(v)）がカット候補。

3確率解析と試行回数
1回の正解確率 $\ge \frac{2}{N(N-1)}$。$\frac{N(N-1)}{2} \ln N$ 回試行で失敗確率 $\le \frac{1}{N}$。実用的には N=500 で約 30,000 試行が必要だが、制限内に収める調整が必要。

4全試行の最小値を採用
各試行の結果の最小値が答え。試行回数が多いほど高確率で正解に近づく。

計算量

1回の試行: $O(M \alpha(N))$
試行回数（基本版）: $O(N^2 \log N)$
全体（基本版）: $O(M N^2 \log N)$
Karger-Stein 高速版: $O(N^2 \log^3 N)$
Stoer-Wagner（決定論的）: $O(N^3)$ または $O(MN + N^2 \log N)$

よくあるミス

ミス	原因	正しい書き方
縮約後に自己ループを除去する	カット数が過小評価される	自己ループは削除、多重辺は保持
試行回数が少なすぎる	確率的失敗	$N^2 \log N$ 以上の試行数を設定
st-最小カットと混同する	グローバル最小カットと別物	全試行の最小値をとる（st 固定なし）
components の初期値がずれる	頂点番号 0-indexed/1-indexed の混乱	頂点番号の扱いを統一する

次のステップ

発展問題: Karger-Stein アルゴリズム（再帰的縮約で $O(N^2 \log^3 N)$）
関連: Stoer-Wagner アルゴリズム（決定論的 $O(N^3)$）
応用: グローバル最小カットの辺集合復元、k-辺連結成分分解

自己評価

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