設問と適用場面
プログラマーへの問題の割り当ては有用なモデルです。左側に問題、右側にプログラマーがあり、辺は双方が必要なタグを共有していることを意味します。各辺は最大1回しか選択できず、目標は割り当て数を最大化することです。PracHub の公開面接課題では、この適格性割り当てを二部マッチングとしてモデル化し、辺の生成、分散調整、ストリーミング変更へと拡張しています。本記事では、単一マシンでのコーディングの中核に焦点を当てます。
面接官が見ているポイント
- 実行可能マッチング、極大マッチング、最大要素数マッチングの違いを区別できるか。
- 不変条件を維持しながらマッチングを拡張できる理由を、増加道を用いて説明できるか。
- 頂点素な最短増加道の集合を求めるための BFS の層別化と DFS を説明できるか。
- 最悪計算量 O((V+E)√V)、記憶領域 O(V+E)、およびアルゴリズムの限界を提示できるか。
最初に確認すべき明確化のための質問
- 目標は最大要素数マッチングか、それとも重み、優先度、公平性の制約があるか。
- n、m、E の制約範囲はいくつか、また入力はすでに二部グラフであり重複辺はないか。
- 出力はサイズのみでよいか、それともすべてのペアと未マッチングの頂点も返す必要があるか。
- グラフは静的なバッチか、それともオンラインのレイテンシ目標の下で辺が挿入・削除されるか。
30秒で答える要約
「2つのオブジェクトクラスを二部グラフの両側としてモデル化し、適格性を辺として表現します。pair_left と pair_right を保持します。各 BFS はすべての未マッチングの左側頂点から開始し、未マッチング辺とマッチング済み辺を交互に通って層（レイヤー）を構築します。次に DFS はその層別グラフ内で頂点素な最短増加道の集合を見つけ、各パスを反転することでマッチングを増やします。増加道が存在しなくなったとき、増加道定理により最大マッチングが得られます。最悪時間計算量は O((V+E)√V) です。小規模なグラフであれば、より単純な DFS による増加道の実装でも十分な場合があります。」
ステップ別の解決手順
ステップ 1: グラフの構築と不変条件
隣接リストには実際に実現可能な辺のみを格納します。pair_left[u] と pair_right[v] は互いを指すか、あるいは両方が -1 である必要があります。1つの増加道を反転しても変化するのはそのパス上の辺のみであるため、どの頂点にも2本以上のマッチング辺が接続されることはありません。
ステップ 2: BFS による層の構築
すべての未マッチングの左側頂点から同時に開始します。未マッチング辺を通って右側へ進み、マッチング済み辺を通って左側頂点へ戻りながら、最短の層を記録します。未マッチングの右側頂点に到達できる最短層を保持することで、DFS が同じフェーズでより長いパスを探索しないようにします。
ステップ 3: DFS によるバッチ増加
各未マッチングの左側頂点から DFS を実行します。未マッチングの右側頂点に到達すれば成功です。マッチング済みの右側頂点に到達した場合は、層が1つだけ増加している場合に限り、そのマッチング相手の左側頂点へと再帰します。左側頂点ごとの隣接カーソルを用いることで、同一フェーズ内で失敗した辺の再走査を防ぎます。
ステップ 4: 正当性と停止性
増加道はマッチング済み辺よりも未マッチング辺が1本多いため、それに沿って対称差を取ると要素数が1増加します。増加道定理によると、増加道が存在しないこととマッチングが最大であることは同値です。各フェーズでマッチングが増加するため、ループは必ず終了します。
ステップ 5: 計算量とトレードオフ
Hopcroft–Karp 法の最悪時間計算量は O((V+E)√V)、補助空間は O(V)、グラフの記憶領域は O(V+E) です。Princeton の参照実装では最小頂点被覆も導出していますが、この設問ではマッチングのみが必要です。小規模なグラフの場合、左側ごとの DFS のほうが実装は短いですが、最悪ケースで O(VE) かかる可能性があります。重み付きの目的の場合は、代わりにハンガリアン法や最小費用流が必要です。
実行可能な Python 実装
from collections import deque
def hopcroft_karp(left_size, right_size, edges):
adj = [[] for _ in range(left_size)]
for left, right in edges:
adj[left].append(right)
pair_left = [-1] * left_size
pair_right = [-1] * right_size
distance = [-1] * left_size
def bfs():
queue = deque()
for left in range(left_size):
if pair_left[left] == -1:
distance[left] = 0
queue.append(left)
else:
distance[left] = -1
found = False
while queue:
left = queue.popleft()
for right in adj[left]:
mate = pair_right[right]
if mate == -1:
found = True
elif distance[mate] == -1:
distance[mate] = distance[left] + 1
queue.append(mate)
return found
def dfs(left, next_edge):
while next_edge[left] < len(adj[left]):
right = adj[left][next_edge[left]]
next_edge[left] += 1
mate = pair_right[right]
if mate == -1 or (
distance[mate] == distance[left] + 1
and dfs(mate, next_edge)
):
pair_left[left] = right
pair_right[right] = left
return True
distance[left] = -1
return False
matching = 0
while bfs():
next_edge = [0] * left_size
for left in range(left_size):
if pair_left[left] == -1 and dfs(left, next_edge):
matching += 1
return matching, pair_left高評価な回答例
「まず目的が重み付きマッチングではなく最大要素数であることを確認し、適格性を二部グラフの辺としてモデル化します。2つのペア配列で双方向の不変条件を維持します。BFS がすべての未マッチングの左側頂点から最短増加道を層別化し、DFS が現在辺カーソルを用いてその層グラフ内で可能な限り多くの頂点素なパスを見つけ、それらの辺を反転させます。パスが残っていなければ、増加道定理により最適性が証明されます。この実装の時間計算量は O((V+E)√V)、記憶領域は O(V+E) です。小規模なグラフであれば単純な DFS も使えますが、重み付きの目的にはハンガリアン法や最小費用流が必要となります。」
よくある間違い
- 貪欲法の結果を最大と呼んでしまうこと。極大マッチングは最大マッチングより大幅に小さくなることがあります。
- 各ペアの片側しか保存せず、反転後に重複割り当てを発生させてしまうこと。
- BFS を到達可能な任意のパスで停止してしまい、最短層のバッチ処理を崩してしまうこと。
- 現在辺カーソルを省略し、1つのフェーズ内で失敗した辺を再走査してしまうこと。
- 一般グラフ、重み付き、または動的に更新されるマッチングに対して O((V+E)√V) だと主張すること。
フォローアップ質問と効果的な回答
すべての n×m ペアを比較せずに適格性の辺を生成するにはどうすればよいですか？
タグによる転置インデックスを構築します。右側のオブジェクトをバケット化し、各左側オブジェクトに対してそれらのバケットを結合して重複を排除します。それでも E が大きくなる可能性があるため、E の大きさ、頻出タグ（ホットタグ）の偏り、メモリ制限について言及してください。
なぜ増加道が存在しないときにアルゴリズムを終了できるのですか？
すべての増加道はマッチングのサイズを1つ増やします。増加道定理は、より大きなマッチングが存在することと増加道が存在することが同値であると述べているため、増加道が見つからないことは最大要素数であることの証明になります。
重み付きの選好がある場合、何が変わりますか？
Hopcroft–Karp 法は辺の数のみを最適化します。ハンガリアン法または最小費用最大流を使用し、計算量、整数重みの制限、実行可能な割り当てが存在しない場合のフォールバックを改めて説明します。
継続的な辺の追加・削除（チャーン）にはどう対処しますか？
バッチアルゴリズムは再計算に適しています。オンラインサービスでは影響を受ける頂点の周囲で増加道を局所的に探索できますが、レイテンシ、再割り当ての制限、および一時的な非最適性の許容条件を明示する必要があります。