問題
$|L|$ 頂点と $|R|$ 頂点からなる二部グラフが与えられる。最大独立集合（どの辺も両端を含まない最大の頂点部分集合）のサイズと構成を出力せよ。
König定理による復元手順を使うこと：最大独立集合 = $N$ − 最小頂点被覆 = $N$ − 最大マッチング。
制約
$1 \le |L|, |R| \le 10^5$
$0 \le M \le 2 \times 10^5$
時間制限: 2sec / メモリ: 256MB
入出力例
入力例 1
3 3 5
1 1
1 2
2 2
2 3
3 3出力例 1
4
L: 3
R: 1 2概念図: König定理による最小頂点被覆の復元
ヒント（段階的開示）
ヒント1: 方向性
König定理: 二部グラフにおいて「最大マッチング」 = 「最小頂点被覆」。最大独立集合 = $N$ − 最小頂点被覆。一般グラフでは NP 困難だが二部グラフでは多項式時間。
ヒント2: 最小頂点被覆の復元
- Hopcroft-Karp で最大マッチング $M^*$ を求める。
- マッチングに使われていない $L$ 側頂点 $U$ から出発し、交互路BFS。
- 到達可能な $R$ 側頂点 + 到達不可能な $L$ 側頂点 = 最小頂点被覆。
- その補集合 = 最大独立集合。
ヒント3: 実装骨格
# König の復元
unmatched_L = {v for v in range(1, NL+1) if match_L[v] == -1}
reachable_L, reachable_R = set(unmatched_L), set()
queue = deque(unmatched_L)
while queue:
u = queue.popleft()
for v in graph[u]:
if v not in reachable_R:
reachable_R.add(v)
w = match_R[v] # マッチング辺でRからLへ
if w != -1 and w not in reachable_L:
reachable_L.add(w)
queue.append(w)
# 最大独立集合
indep_L = reachable_L
indep_R = set(range(1, NR+1)) - reachable_R模範解答 (Python)
import sys
from collections import deque
input = sys.stdin.readline
def solve():
NL, NR, M = map(int, input().split())
graph = [[] for _ in range(NL + 1)]
for _ in range(M):
l, r = map(int, input().split())
graph[l].append(r)
# Hopcroft-Karp
INF = float('inf')
match_L = [-1] * (NL + 1)
match_R = [-1] * (NR + 1)
dist = [0] * (NL + 1)
def bfs():
queue = deque()
for u in range(1, NL + 1):
if match_L[u] == -1:
dist[u] = 0
queue.append(u)
else:
dist[u] = INF
found = False
while queue:
u = queue.popleft()
for v in graph[u]:
w = match_R[v]
if w == -1:
found = True
elif dist[w] == INF:
dist[w] = dist[u] + 1
queue.append(w)
return found
def dfs(u):
for v in graph[u]:
w = match_R[v]
if w == -1 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, NL + 1):
if match_L[u] == -1:
if dfs(u):
matching += 1
# König: 交互路BFSで到達可能頂点を発見
reachable_L = set()
reachable_R = set()
queue = deque()
for u in range(1, NL + 1):
if match_L[u] == -1:
reachable_L.add(u)
queue.append(u)
while queue:
u = queue.popleft()
for v in graph[u]:
if v not in reachable_R:
reachable_R.add(v)
w = match_R[v]
if w != -1 and w not in reachable_L:
reachable_L.add(w)
queue.append(w)
# 最大独立集合
indep_L = sorted(reachable_L)
indep_R = sorted(set(range(1, NR + 1)) - reachable_R)
total = len(indep_L) + len(indep_R)
print(total)
print("L:", *indep_L)
print("R:", *indep_R)
solve()
Step-by-Step 解説
1König定理の確認
二部グラフ $G$ では：最大マッチング = 最小頂点被覆（König定理）。最大独立集合 = $N$ − 最小頂点被覆。一般グラフでは最大独立集合はNP困難だが、二部グラフでは多項式時間で解ける。
二部グラフ $G$ では：最大マッチング = 最小頂点被覆（König定理）。最大独立集合 = $N$ − 最小頂点被覆。一般グラフでは最大独立集合はNP困難だが、二部グラフでは多項式時間で解ける。
2Hopcroft-Karp法
BFSで増加路の最短距離を計算し、DFSで複数の増加路を同時に見つける。$O(\sqrt{N} \cdot M)$ の効率的な最大二部マッチング。
BFSで増加路の最短距離を計算し、DFSで複数の増加路を同時に見つける。$O(\sqrt{N} \cdot M)$ の効率的な最大二部マッチング。
3最小頂点被覆の復元（König）
未マッチの $L$ 側頂点から交互路（未マッチ辺 → マッチ辺 → 未マッチ辺 → ...）でBFS。到達可能な $R$ 側 + 到達不可能な $L$ 側 = 最小頂点被覆。
未マッチの $L$ 側頂点から交互路（未マッチ辺 → マッチ辺 → 未マッチ辺 → ...）でBFS。到達可能な $R$ 側 + 到達不可能な $L$ 側 = 最小頂点被覆。
4最大独立集合の導出
最小頂点被覆の補集合。$L$ 側: 交互路で到達可能、$R$ 側: 到達不可能な頂点。
最小頂点被覆の補集合。$L$ 側: 交互路で到達可能、$R$ 側: 到達不可能な頂点。
5正確さの確認
選ばれた頂点集合を全辺について検証：辺の両端が同時に独立集合に含まれる辺がないことを確認。
選ばれた頂点集合を全辺について検証：辺の両端が同時に独立集合に含まれる辺がないことを確認。
計算量
Hopcroft-Karp: $O(\sqrt{N} \cdot M)$
König 復元BFS: $O(N + M)$
全体: $O(\sqrt{N} \cdot M)$
König 復元BFS: $O(N + M)$
全体: $O(\sqrt{N} \cdot M)$
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| 交互路の方向を逆に | L→R は未マッチ辺、R→L はマッチ辺 | 正しく方向を管理 |
| 最小頂点被覆と最大独立集合の混同 | 補集合関係 | indep = V - cover |
| 未マッチの L 頂点全てを起点に | BFSの初期化 | 全ての未マッチ L 頂点をキューに |
| 一般グラフに適用 | König定理は二部グラフのみ | 二部性の確認が必要 |
次のステップ
- 発展問題: 重み付き最小頂点被覆（最小カット = 最大流で解く）
- 応用: Project Selection Problem（最大重みクロージャの特殊ケース）
- 類題: AtCoder ABC 313 F, ARC 092 F など二部グラフ系問題