Day 142-Q4 — Nash-Williams森分解（マトロイド合併によるk-辺連結性のスパース証明書）

2026-09-03 赤色 Master / Phase 8+ ★★★★★★★★★ K本のUnion-Findへ辺を貪欲割り当てO(MKα(N))でスパース化

問題

$N$頂点$M$辺の無向グラフ（多重辺・自己ループなし）と整数$K$が与えられる。辺は入力順に$1$〜$M$の番号を持つ。

以下の貪欲な森分解アルゴリズムに従って、各辺が証明書に含まれるかを判定せよ。

アルゴリズムの定義

$K$本の森$F_1,\dots,F_K$（Union-Findで管理）を空の状態から用意する。辺を入力順に処理し、辺$(u,v)$に対して$i=1,\dots,K$の順に「$F_i$上で$u,v$がまだ非連結か」を調べ、最小の$i$でサイクルができないなら$F_i$に加える。どの$F_i$でもサイクルができるなら証明書から除外する。

各辺について、証明書に含まれるなら1、除外されるなら0を出力せよ。

入力形式

N M K
u_1 v_1
:
u_M v_M

制約

$2 \le N \le 2\times10^5$
$1 \le M \le 2\times10^5$
$1 \le K \le 20$
$1 \le u_i,v_i \le N$、$u_i\ne v_i$

入出力例

入力例1 (K=1)

4 6 1
1 2
2 3
3 4
4 1
1 3
2 4

出力例1

1
1
1
0
0
0

入力例2 (K=2)

4 6 2
1 2
2 3
3 4
4 1
1 3
2 4

出力例2

1
1
1
1
1
1

概念図

K=1: K4の6辺を1本の森に貪欲割り当て（3辺のみ収まる） F1（森・辺 1-2, 2-3, 3-4 が収まる） 1 2 3 4 除外された辺（F1で既に連結・サイクルになる） 4-1（サイクル） 1-3（サイクル） 2-4（サイクル） K=2なら2本目の森F2にこの3辺が全て収まり出力は全て1になる

ヒント（段階的開示）

ヒント1（方向性）

「グラフがサイクルを作らないように辺を選ぶ」操作は、グラフィックマトロイド上の独立集合の拡張である。1本のUnion-Findでこれを行えば最大全域森が求まるが、これを$K$回、前の森で使わなかった辺だけを対象に繰り返すことで$K$個のマトロイドの合併（matroid union）が実現できる。

ヒント2（アプローチ）

Nash-Williams/Tutteの定理により、この貪欲な$K$本森分解で除外されなかった辺集合（証明書）だけを使っても、元のグラフの最小カットが$K$未満かどうかを正しく判定できる。証明書のサイズは高々$K(N-1)$本になり、$M$が大きくても大幅に間引ける。

ヒント3（誘導） 
def build_certificate(n, edges, k):
    parent = [list(range(n + 1)) for _ in range(k)]
    def find(f, x):
        while parent[f][x] != x:
            parent[f][x] = parent[f][parent[f][x]]
            x = parent[f][x]
        return x
    def union(f, x, y):
        rx, ry = find(f, x), find(f, y)
        if rx == ry:
            return False
        parent[f][rx] = ry
        return True

    kept = []
    for (u, v) in edges:
        placed = False
        for f in range(k):
            if union(f, u, v):
                placed = True
                break
        kept.append(1 if placed else 0)
    return kept

模範解答 (Python)

import sys

def main():
    data = sys.stdin.read().split()
    idx = 0
    n, m, k = int(data[idx]), int(data[idx+1]), int(data[idx+2]); idx += 3

    parent = [list(range(n + 1)) for _ in range(k)]

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

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

    out = []
    for _ in range(m):
        u, v = int(data[idx]), int(data[idx+1]); idx += 2
        placed = False
        for f in range(k):
            if union(f, u, v):
                placed = True
                break
        out.append("1" if placed else "0")

    print("\n".join(out))

main()

Step-by-Step 解説

11本の森分解 = 最大全域森
K=1の場合はUnion-Findで辺を順に見てサイクルを作る辺を除外する、Kruskal法のUnion-Find部分と同じ操作になる。
2複数の森への割り当て
K≥2のとき、F1で弾かれた辺はF2に「もう一度挑戦」する機会が与えられる。辺は最初にサイクルを作らずに収まる森に割り当てられる。
3証明書になる理由
Nash-Williams/Tutteのマトロイド合併定理により、この貪欲法で除外されなかった辺だけを残しても元のグラフがK-辺連結かどうかの判定結果は変わらないことが保証される。
4証明書のサイズ
K本の森はそれぞれ高々N-1本の辺しか持てないため、証明書に残る辺の総数は高々K(N-1)本。密なグラフでも大幅に間引ける。
5計算量
各辺につき最大K回のfind/unionを行うので全体でO(MKα(N))。K≤20程度ならM=2×10^5でも十分高速。

よくあるミス

ミス原因正しい書き方
辺を1本のUnion-Findだけで判定し最初の森で弾かれた辺をそのまま除外K=1の最大全域森の考え方から抜け出せていないK本の独立したUnion-Findを用意し順に試す
K本のUnion-Findを1つの配列で共有してしまうparentを森ごとに分けずに使い回している森ごとに独立したparent配列を用意する
辺の割り当てを最後の森から順に試してしまう貪欲法の走査順序を逆にしている必ず小さい番号の森から順に試す
経路圧縮を実装せずfindがO(N)になり全体がO(MKN)に悪化Union-Findの高速化を省略しているfindに経路圧縮を実装する
証明書に残った辺だけで最短路や連結成分数まで保存されると誤解する証明書が保証するのはK-辺連結性の判定に限られることを理解していない証明書は最小カットがK未満かどうかの判定用と理解する

次のステップ

  • 発展: 得られた証明書に対してStoer-Wagner法（Day095/Day115）を適用し、密なグラフでの大域最小カット計算を高速化せよ。証明書を使わない場合との実行時間比較を行うこと。
  • 発展2: 辺をランダムな順序でシャッフルしてから処理した場合に、証明書に残る辺の総数や構成がどう変化するかを実験的に観察せよ。

自己評価

自分の回答

気づき・メモ