Day 095-Q2 — 一般グラフ最大マッチング（Edmonds' Blossom Algorithm）

2026-07-17 赤色 Master / Phase 8+ ★★★★★★★★★ ブロッサム縮約・奇閉路処理

問題

$N$ 頂点 $M$ 辺の（二部グラフとは限らない、一般の）無向グラフが与えられる。頂点を共有しない辺の集合（マッチング）のうち、辺数が最大となるものを1つ求めよ。

二部グラフであれば増加路アルゴリズムで解けるが、奇閉路が存在する一般グラフでは単純な増加路探索が機能しない。奇閉路を1つの頂点（ブロッサム）に縮約しながら増加路を探す Edmonds' Blossom Algorithm を実装せよ。

入力形式

N M
u_1 v_1
:
u_M v_M

制約

$1 \le N \le 300$
$0 \le M \le \frac{N(N-1)}{2}$
単純グラフ（自己ループ・多重辺なし）

入出力例

入力例1

5 5
1 2
2 3
3 4
4 5
5 1

出力例1

2
1 2 3 4 0

5頂点の奇閉路（5-サイクル）。最大マッチングは2（辺 1-2, 3-4、頂点5は非マッチング）。2行目は各頂点の相手（1-indexed、非マッチングは0）。

概念図

奇閉路の検出とブロッサム縮約 v1 v2 v3 v4 v5 奇閉路 (v1..v5) を検出 → 1つの頂点baseに縮約 base 縮約後は base を1頂点として探索を継続。増加路が見つかれば parent[]を辿って元の頂点列に復元し、マッチング辺を反転する

ヒント（段階的開示）

ヒント1: 方向性
二部グラフの増加路アルゴリズムをそのまま一般グラフに適用すると、奇閉路を経由する場合に「どちらが未マッチング側か」の判定が壊れて誤った増加路を見つけてしまう。奇閉路を特別扱いする仕組みが必要。
ヒント2: アプローチ
未マッチング頂点からBFSで交互路を探す。探索中に奇閉路（ブロッサム）を検出したら、そのサイクル全体を1つの頂点に縮約して探索を継続する。ブロッサムの根は base[] 配列で管理し、縮約前の頂点への経路復元は parent[] 配列を使う。増加路が見つかったら経路に沿ってマッチング辺と非マッチング辺を反転する。
ヒント3: 誘導（コード骨格） 
def find_path(root, n, adj, match, parent, base):
    used = [False]*n
    for i in range(n): base[i] = i
    used[root] = True
    q = deque([root])
    while q:
        v = q.popleft()
        for to in adj[v]:
            if base[v] == base[to] or match[v] == to:
                continue
            if to == root or (match[to] != -1 and parent[match[to]] != -1):
                curbase = lca(v, to, match, parent, base, n)
                # v-to のサイクルをcurbaseに縮約
                ...
            elif parent[to] == -1:
                parent[to] = v
                if match[to] == -1:
                    return to          # 増加路発見
                used[match[to]] = True
                q.append(match[to])
    return -1

lca(v, to) は「$v$ と $to$ からマッチング辺を遡って合流する頂点（ブロッサムの根）」を求める処理。

模範解答 (Python)

import sys
from collections import deque


def max_matching(n, adj):
    match = [-1] * n
    parent = [-1] * n
    base = list(range(n))
    used = [False] * n
    in_blossom = [False] * n

    def lca(a, b):
        seen = [False] * n
        x = a
        while True:
            x = base[x]
            seen[x] = True
            if match[x] == -1:
                break
            x = parent[match[x]]
        y = b
        while True:
            y = base[y]
            if seen[y]:
                return y
            y = parent[match[y]]

    def mark_path(v, b, child):
        while base[v] != b:
            in_blossom[base[v]] = True
            in_blossom[base[match[v]]] = True
            parent[v] = child
            child = match[v]
            v = parent[match[v]]

    def find_path(root):
        nonlocal used, parent, base
        used = [False] * n
        parent = [-1] * n
        for i in range(n):
            base[i] = i
        used[root] = True
        q = deque([root])
        while q:
            v = q.popleft()
            for to in adj[v]:
                if base[v] == base[to] or match[v] == to:
                    continue
                if to == root or (match[to] != -1 and parent[match[to]] != -1):
                    curbase = lca(v, to)
                    for i in range(n):
                        in_blossom[i] = False
                    mark_path(v, curbase, to)
                    mark_path(to, curbase, v)
                    for i in range(n):
                        if in_blossom[base[i]]:
                            base[i] = curbase
                            if not used[i]:
                                used[i] = True
                                q.append(i)
                elif parent[to] == -1:
                    parent[to] = v
                    if match[to] == -1:
                        return to
                    used[match[to]] = True
                    q.append(match[to])
        return -1

    for v in range(n):
        if match[v] == -1:
            u = find_path(v)
            if u != -1:
                while u != -1:
                    pv = parent[u]
                    ppv = match[pv]
                    match[u] = pv
                    match[pv] = u
                    u = ppv
    return match


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

    adj = [[] for _ in range(n)]
    for _ in range(m):
        a = int(data[idx]) - 1; idx += 1
        b = int(data[idx]) - 1; idx += 1
        adj[a].append(b)
        adj[b].append(a)

    match = max_matching(n, adj)
    size = sum(1 for x in match if x != -1) // 2
    print(size)
    print(' '.join(str(x + 1 if x != -1 else 0) for x in match))


main()
計算量: 頂点ごとに1回 find_path（BFS $O(N+M)$ + ブロッサム縮約 $O(N)$）を最大 $O(N)$ 回呼ぶため、全体で $O(N^3)$。

Step-by-Step 解説

1増加路探索の基本構造
未マッチング頂点からBFSで交互路（非マッチング辺→マッチング辺→…）を辿る。
2ブロッサムの検出（lca）
両端が既に到達可能な辺を見つけたら奇閉路の存在を意味し、lcaでその根を特定する。
3縮約（mark_path + base更新）
閉路上の全頂点のbaseを根に付け替え、以後1頂点として扱う。parentは元の頂点を指すため後で復元可能。
4増加路の反転
未マッチング頂点に到達したらparentを遡りマッチング辺と非マッチング辺を入れ替える。

よくあるミス

ミス原因正しい書き方
二部グラフ用の単純な増加路DFSを流用してしまう奇閉路の存在を考慮していないブロッサム縮約（base/lca/mark_path）を実装する
縮約後に used フラグの更新を忘れて探索が止まる新しく到達可能になった頂点をキューに積み忘れるin_blossom[base[i]] なら used[i] を確認しキューに追加
lca で seen 配列を使い回してしまう前回の探索結果が残り誤判定呼び出しごとに新しい配列を用意する
増加路反転時に更新順序を間違える経路復元ロジックの誤りpv = parent[u]; ppv = match[pv] を先に読んでから更新

次のステップ

  • 発展: 重み付き一般グラフ最大マッチング（Galil's algorithm・双対変数とスラック管理）
  • 発展: マトロイド交差との構造的類似性
  • 次回予告: Suffix Automaton拡張（辞書順K番目相異なる部分文字列）

自己評価

自分の回答

気づき・メモ