Day 113-Q2 — Hopcroft-Karp法（二部グラフ最大マッチング O(E√V)）

2026-08-05 赤色 Master / Phase 8+ ★★★★★★★★★ BFSレベル分割 + 複数増加路DFS

問題

左側頂点が $N$ 個（$1$〜$N$）、右側頂点が $M$ 個（$1$〜$M$）の二部グラフがあり、辺が $E$ 本与えられる。この二部グラフの最大マッチング（互いに頂点を共有しない辺の最大個数の組）を求め、マッチング数と共に組の一覧を出力せよ。

入力形式

N M E
a_1 b_1
a_2 b_2
...
a_E b_E

制約

$1 \le N, M \le 2\times10^5$
$0 \le E \le 2\times10^5$
$1 \le a_i \le N,\ 1\le b_i \le M$
同じ辺が複数回与えられることはない

入出力例

入力例1

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

出力例1

3
1 2
2 1
3 3

最大マッチングのサイズは3。組み合わせは複数あり得るがサイズが3であれば正解。

入力例2

2 2 1
1 1

出力例2

1
1 1

概念図: BFSでレベル分割し複数の増加路を同時に反転する

1回のBFS+DFSフェーズで複数の最短増加路をまとめて反転 a1 a2 a3 b1 b2 b3 黄線 = 現フェーズで見つかる増加路（頂点を共有しない） これらは同時に反転してよい（マッチング+3） dist[a2] == dist[a]+1 の辺だけをDFSで辿る ことでレベルグラフ上の最短路のみ探索する フェーズ数は O(√V) 回に理論的に抑えられる → 全体 O(E√V)

ヒント（段階的開示）

ヒント1: 方向性
単純な貪欲法（Kuhn's algorithm、1本ずつ増加路をDFSで探す）でも最大マッチングは求まるが計算量は $O(VE)$。$2\times10^5$規模だと間に合わない。複数の増加路を同時に、しかも最短のものから見つけることで計算量を $O(E\sqrt V)$ に落とせるのが Hopcroft-Karp法。
ヒント2: アプローチ
2フェーズを交互に繰り返す。①BFSフェーズ: 未マッチ左側頂点全てを始点にBFSし各頂点への最短距離を求める。未マッチ右側頂点に到達できたら増加路の存在が分かる。②DFSフェーズ: 距離が単調増加する経路（レベルグラフ）だけを辿ってDFSし、複数の増加路をまとめて反転する。増加路が見つからなくなったら終了。
ヒント3: 誘導（コード骨格） 
def dfs(a, dist):
    for b in g[a]:
        a2 = matchR[b]
        if a2 == 0 or (dist[a2] == dist[a] + 1 and dfs(a2, dist)):
            matchL[a] = b; matchR[b] = a
            return True
    dist[a] = INF
    return False

模範解答 (Python)

import sys
from collections import deque

def main():
    data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(data[idx]); idx += 1
    M = int(data[idx]); idx += 1
    E = int(data[idx]); idx += 1
    g = [[] for _ in range(N + 1)]
    for _ in range(E):
        a = int(data[idx]); idx += 1
        b = int(data[idx]); idx += 1
        g[a].append(b)

    matchL = [0] * (N + 1)
    matchR = [0] * (M + 1)
    INF = float('inf')

    def bfs():
        dist = [0] * (N + 1)
        q = deque()
        for a in range(1, N + 1):
            if matchL[a] == 0:
                dist[a] = 0
                q.append(a)
            else:
                dist[a] = INF
        found = False
        while q:
            a = q.popleft()
            for b in g[a]:
                a2 = matchR[b]
                if a2 == 0:
                    found = True
                elif dist[a2] == INF:
                    dist[a2] = dist[a] + 1
                    q.append(a2)
        return dist, found

    def dfs(a, dist):
        for b in g[a]:
            a2 = matchR[b]
            if a2 == 0 or (dist[a2] == dist[a] + 1 and dfs(a2, dist)):
                matchL[a] = b
                matchR[b] = a
                return True
        dist[a] = INF
        return False

    sys.setrecursionlimit(400000)
    matching = 0
    while True:
        dist, found = bfs()
        if not found:
            break
        for a in range(1, N + 1):
            if matchL[a] == 0:
                if dfs(a, dist):
                    matching += 1

    out = [str(matching)]
    for a in range(1, N + 1):
        if matchL[a] != 0:
            out.append(f"{a} {matchL[a]}")
    print("\n".join(out))

main()
計算量: $O(E\sqrt V)$。ランダム二部グラフ（$N=M=2000, E=8000$）で実測0.03秒程度。Kuhn's algorithmとの出力サイズ一致、出力ペアが辺集合に含まれ左右重複がないことをランダムテストで確認済み。

Step-by-Step 解説

1隣接リストで辺を持つ
左側頂点ごとに接続する右側頂点のリストを持つ。
2BFSでレベル（距離）を計算する
未マッチ左側頂点を距離0としてBFSし、辺→マッチ相手への逆辺、で距離を伝播する。
3DFSでは距離が単調増加する経路だけを辿る
dist[a2]==dist[a]+1の条件でレベルグラフ上のみDFSし、増加路同士が頂点を共有しないことを保証する。
4増加路が見つからなくなったら終了
BFSで未マッチ右側頂点に到達できなくなった時点が最大マッチング。
5フェーズ数がO(√V)に抑えられる理由
最短増加路の長さがフェーズごとに真に増加していくため。

よくあるミス

ミス原因正しい書き方
未マッチ右側頂点を見つけた時点でBFSを打ち切る複数増加路の同時発見という利点が失われるfound=Trueにした後も他頂点への距離計算を続行する
DFSで距離条件を付けない単なるKuhn法O(VE)に退化するレベルグラフ上のみを辿る条件を必ず付ける
dfs失敗ノードのdistをINFにしない同じフェーズ内で同じ失敗探索を繰り返す失敗時にdist[a]=INFとして枝刈りする
出力ペアの整合性を未検証のままにするマッチングの左右重複に気づかないmatchL[a]!=0の頂点のみ出力すれば自動的に重複なし

次のステップ

  • 発展: 重み付き二部マッチング（Hungarian Algorithm、Day050 Q3 / Day059 Q3）との使い分けを整理する
  • 発展: 一般グラフの最大マッチング（Blossom Algorithm、Day019 Q3 / Day095 Q2）との実装差を比較する
  • 発展: Dinic法を単位容量フローとして実装し同じ O(E√V) になることを確認する

自己評価

自分の回答

気づき・メモ