Day 092-Q2 — Hopcroft-Karp（最大二部マッチング）

問題

左側 $N$ 頂点・右側 $M$ 頂点・$E$ 辺の二部グラフが与えられる。最大マッチング（両端点を共有しない辺集合の最大サイズ）を求めよ。

入出力例

3 3 4
1 1
1 2
2 1
3 3

3

$1\text{-}2,\ 2\text{-}1,\ 3\text{-}3$ で3本マッチできる。

概念図

ヒント

while bfs():
    for u in range(1, N + 1):
        if matchL[u] == 0 and dfs(u):
            res += 1

模範解答

import sys
from collections import deque

def main():
    data = sys.stdin.buffer.read().split()
    idx = 0
    n = int(data[idx]); m = int(data[idx + 1]); e = int(data[idx + 2]); idx += 3
    g = [[] for _ in range(n + 1)]
    for _ in range(e):
        u = int(data[idx]); v = int(data[idx + 1]); idx += 2
        g[u].append(v)

    INF = float('inf')
    matchL = [0] * (n + 1)   # 左u のマッチ先（0=未マッチ）
    matchR = [0] * (m + 1)   # 右v のマッチ先
    dist = [0] * (n + 1)

    def bfs():
        dq = deque()
        for u in range(1, n + 1):
            if matchL[u] == 0:
                dist[u] = 0
                dq.append(u)
            else:
                dist[u] = INF
        found = False
        while dq:
            u = dq.popleft()
            for v in g[u]:
                w = matchR[v]
                if w == 0:
                    found = True          # 未マッチ右に到達＝増加路あり
                elif dist[w] == INF:
                    dist[w] = dist[u] + 1
                    dq.append(w)
        return found

    def dfs(u):
        for v in g[u]:
            w = matchR[v]
            if w == 0 or (dist[w] == dist[u] + 1 and dfs(w)):
                matchL[u] = v
                matchR[v] = u
                return True
        dist[u] = INF
        return False

    res = 0
    while bfs():
        for u in range(1, n + 1):
            if matchL[u] == 0 and dfs(u):
                res += 1
    print(res)

main()

計算量 $O(E\sqrt V)$。密グラフでも Hungarian の $O(VE)$ より高速。

Step-by-Step 解説

Step 1: マッチ配列の初期化

matchL, matchR を 0（未マッチ）で初期化。0 を「無し」の番兵に使う。

Step 2: BFS で層グラフを作る

全未マッチ左頂点を距離0で開始。マッチ辺を逆向きに辿って距離ラベルを伝播。未マッチ右に到達したら増加路が存在。

Step 3: DFS で頂点素な増加路を流す

Step 4: フェーズ反復

BFS が増加路を見つける限り繰り返す。最短増加路長は毎フェーズ増えるためフェーズ数 $O(\sqrt V)$。

よくあるミス

次のステップ

• 発展: König の定理で最小頂点被覆・最大独立集合を復元
• 発展: 重み付きは Hungarian（KM法）や MCMF
• 次回予告: Z-algorithm（文字列の最小周期）

自己評価