Day 016-Q3 — Hall の定理と完全マッチング条件

2026-04-29 赤色 Master / Phase 8+ ★★★★★★★★★ Hall / 二部マッチング

問題

$L$ 頂点と $R$ 頂点からなる二部グラフが与えられる（$|L| = |R| = N$）。左側の頂点集合 $L = \{l_1, \ldots, l_N\}$、右側 $R = \{r_1, \ldots, r_N\}$、辺集合 $E$。

Hall 条件（完全マッチングの必要十分条件）を確認し、完全マッチングが存在するか判定せよ。

存在する場合: YES と完全マッチング（各 $l_i$ に対応する $r_j$）を出力。存在しない場合: NO と Hall 条件を破る最小の証拠集合 $S \subseteq L$（$|N(S)| < |S|$ となる $S$）を出力。

入力形式

N M
u_1 v_1
u_2 v_2
...
u_M v_M

（辺は $l_u \to r_v$ を意味する）

制約

$1 \le N \le 500$
$0 \le M \le N^2$

入出力例

入力例 1

3 4
1 1
1 2
2 2
3 3

出力例 1

YES
1 2
2 1
3 3

（l1→r2, l2→r1, l3→r3 等、完全マッチングなら何でも可）

入力例 2

3 2
1 1
2 1

出力例 2

NO
1 2

（$S = \{l_1, l_2\}$ に対し $N(S) = \{r_1\}$, $|N(S)|=1 < 2=|S|$）

ヒント (段階的開示)

ヒント1: 方向性
完全マッチングの判定は最大マッチングを求めるだけでよい（$|$マッチング$| = N$ なら完全）。Hall 条件の違反集合は最大マッチングから König の定理を用いて構成できる。
ヒント2: アプローチ
  1. 二部グラフの最大マッチングを Hopcroft-Karp で $O(\sqrt{N} \cdot M)$ 計算
  2. |マッチング| < N なら違反集合を構成:
    • König の定理: 最小頂点被覆 = $N -$ 最大マッチング
    • 違反集合 $S$ は「マッチングされていない左頂点から交互路で到達できる左頂点集合」
ヒント3: 誘導 
# Hopcroft-Karp の骨格
def bfs():
    # 距離ラベルを BFS で計算
    # match_l[u] = u にマッチした右頂点（None ならフリー）
    ...

def dfs(u):
    # 増加路を DFS で探索
    ...

模範解答 (Python)

import sys
from collections import deque, defaultdict

def main():
    input_data = sys.stdin.read().split()
    idx = 0
    N, M = int(input_data[idx]), int(input_data[idx+1])
    idx += 2

    adj = defaultdict(list)  # adj[l] = [r1, r2, ...]
    for _ in range(M):
        u, v = int(input_data[idx]), int(input_data[idx+1])
        idx += 2
        adj[u].append(v)

    # Hopcroft-Karp
    INF = float('inf')
    match_l = [0] * (N + 1)   # match_l[l] = r (0 if unmatched)
    match_r = [0] * (N + 1)   # match_r[r] = l
    dist = [0] * (N + 1)

    def bfs():
        queue = deque()
        for u in range(1, N + 1):
            if match_l[u] == 0:
                dist[u] = 0
                queue.append(u)
            else:
                dist[u] = INF
        found = False
        while queue:
            u = queue.popleft()
            for v in adj[u]:
                w = match_r[v]
                if w == 0:
                    found = True
                elif dist[w] == INF:
                    dist[w] = dist[u] + 1
                    queue.append(w)
        return found

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

    matching = 0
    while bfs():
        for u in range(1, N + 1):
            if match_l[u] == 0:
                if dfs(u):
                    matching += 1

    if matching == N:
        print("YES")
        for u in range(1, N + 1):
            print(u, match_l[u])
    else:
        # Hall 条件の違反集合を König の定理で構成
        # 左: マッチングされていない頂点から交互路 BFS
        unmatched_l = {u for u in range(1, N+1) if match_l[u] == 0}
        reachable_l = set(unmatched_l)
        reachable_r = set()
        queue = deque(unmatched_l)
        while queue:
            u = queue.popleft()
            for v in adj[u]:
                if v not in reachable_r:
                    reachable_r.add(v)
                    w = match_r[v]
                    if w != 0 and w not in reachable_l:
                        reachable_l.add(w)
                        queue.append(w)
        # S = reachable_l は Hall 違反集合
        S = sorted(reachable_l)
        print("NO")
        print(*S)

main()

Step-by-Step 解説

1Hall の定理
二部グラフに完全マッチング（$L$ 側完全）が存在 ⟺ 任意の $S \subseteq L$ について $|N(S)| \ge |S|$。
2Hopcroft-Karp で最大マッチング
  • BFS で「増加路の最短長 $d$」を計算
  • DFS で長さ $d$ の増加路を全て一括で探索
  • 各フェーズ $O(M)$、フェーズ数 $O(\sqrt{N})$ → 全体 $O(\sqrt{N} M)$
3König の定理で違反集合を構成
最大マッチングが求まったら、マッチングされていない左頂点から「交互路（非マッチング辺→マッチング辺→…）」でたどれる左頂点集合 $S$ を BFS/DFS。この $S$ が Hall 条件を破る: $|N(S)| = |$到達した右頂点集合$|= |S| - |$フリーな左頂点$|$ となる。
4計算量
$O(\sqrt{N} \cdot M + N)$ — $N=500, M \le 250000$ で十分高速。

よくあるミス

ミス原因正しい書き方
Hopcroft-Karp の BFS でフリー右頂点への処理漏れw == 0 のとき found = True を忘れるif w == 0: found = True を BFS 内に入れる
違反集合を交互路 BFS せず単に unmatched_l を返す$|N(unmatched\_l)|$ が $|unmatched\_l|$ より大きい場合がある正確に交互路 BFS で到達可能集合を計算する

次のステップ

  • 発展問題: 辺に容量・コストが付いた二部グラフで「コスト最小の完全マッチング」（最小費用最大流で解く）

自己評価

自分の回答

気づき・メモ