Day 076-Q5 — 一般マッチング（Blossom Algorithm / Edmonds の花アルゴリズム $O(N^3)$）

問題

$N$ 頂点 $M$ 辺の無向グラフ（一般グラフ）が与えられる。このグラフの最大マッチングのサイズを求めよ。

グラフは奇数長の閉路を含む場合がある（一般グラフ）ことに注意。

入出力例

6 7
1 2
2 3
3 4
4 5
5 6
6 1
3 6

3

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

2

5 頂点の奇数閉路（ペンタゴン）は二部グラフでないため Hopcroft-Karp では解けない。最大マッチングは 2。

概念図: 花（Blossom）の収縮

奇数閉路（花）を 1 頂点 $b$ に収縮すると偶数グラフになり、通常の BFS で増加路を探せる。増加路が見つかったら元に展開する。

ヒント

def lca(a, b):
    vis = [False] * (n + 1)
    while True:
        a = base[a]; vis[a] = True
        if match[a] == -1: break
        a = parent[match[a]]
    while True:
        b = base[b]
        if vis[b]: return b  # LCA発見
        b = parent[match[b]]

# 花の検出時
if u == root or (match[u] != -1 and parent[match[u]] != -1):
    curbase = lca(v, u)
    blossom_vertices = []
    mark_path(v, curbase, u)  # v側の花の頂点をマーク
    mark_path(u, curbase, v)  # u側の花の頂点をマーク
    for bv in blossom_vertices:
        if base[bv] != curbase:
            base[bv] = curbase  # 収縮
            if not used[bv]:
                used[bv] = True; q.append(bv)

模範解答

import sys
from collections import deque
input = sys.stdin.readline

def max_matching(n, adj):
    match = [-1] * (n + 1)

    def find_path(root):
        used = [False] * (n + 1)
        parent = [-1] * (n + 1)
        base = list(range(n + 1))
        used[root] = True
        q = deque([root])

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

        def mark_path(v, b, child):
            while base[v] != b:
                blossom_vertices.append(base[v])
                blossom_vertices.append(base[match[v]])
                parent[v] = child
                child = match[v]
                v = parent[match[v]]

        while q:
            v = q.popleft()
            for u in adj[v]:
                if base[v] == base[u] or match[v] == u:
                    continue
                if u == root or (match[u] != -1 and parent[match[u]] != -1):
                    curbase = lca(v, u)
                    blossom_vertices = []
                    mark_path(v, curbase, u)
                    mark_path(u, curbase, v)
                    for bv in blossom_vertices:
                        if base[bv] != curbase:
                            base[bv] = curbase
                            if not used[bv]:
                                used[bv] = True; q.append(bv)
                elif parent[u] == -1:
                    parent[u] = v
                    if match[u] == -1:
                        while u != -1:
                            pv = parent[u]
                            ppv = match[pv]
                            match[u] = pv; match[pv] = u
                            u = ppv
                        return True
                    u = match[u]
                    used[u] = True; q.append(u)
        return False

    result = 0
    for v in range(1, n + 1):
        if match[v] == -1:
            if find_path(v):
                result += 1
    return result

def main():
    N, M = map(int, input().split())
    adj = [[] for _ in range(N + 1)]
    for _ in range(M):
        u, v = map(int, input().split())
        adj[u].append(v); adj[v].append(u)
    print(max_matching(N, adj))

main()

Step-by-Step 解説

Step 1: Berge の定理

マッチング $M$ が最大 ↔ $M$ に対する増加路が存在しない。増加路: 未マッチ頂点から始まり未マッチ頂点で終わる交互路。見つかれば match を反転して $|M|$ を +1 できる。

Step 2: 二部グラフとの違い

二部グラフでは交互木の BFS で増加路を直接見つけられる（奇数閉路なし）。一般グラフでは BFS 中に奇数閉路（花）が出現し、通常の BFS が正しく動かなくなる。

Step 3: 花（Blossom）の定義

交互木上の 2 つの「偶数距離」頂点を結ぶ辺があるとき奇数閉路（花）が形成される。花の根は LCA（最小共通祖先）で求まる。

Step 4: 花の収縮（Blossoming）

花内の全頂点の base 配列を根に統一する。これにより花が仮想的に 1 頂点になり、その先の BFS を続けられる。

Step 5: マッチングの更新と計算量

増加路発見時: parent を辿りながら match を反転。各頂点から BFS $O(N)$ 回、各 BFS が $O(N^2)$ → 全体 $O(N^3)$。

よくあるミス

次のステップ

• 発展問題: 「一般グラフの最小辺被覆」→ 最大マッチング $|M|$ から $N - |M|$ で計算（König 定理の一般化）

自己評価