題幹與適用場景
例如把題目分配給程式設計師：左側是題目，右側是程式設計師，邊表示至少有一個共同標籤。每條邊最多選一次，目標是最大化分配數量。PracHub 的公開面經把這類資格分配建模成二分圖匹配，並延伸追問邊生成、分散式協調與串流變更；本題聚焦單機編碼部分。
面試官考察點
- 能否區分「任意可行匹配」「極大匹配」與「最大基數匹配」。
- 能否用增廣路證明匹配可繼續變大，並維護匹配不變量。
- 能否解釋 BFS 分層與 DFS 找到一組最短、點不相交的增廣路。
- 能否給出 O((V+E)√V) 的最壞時間、O(V+E) 的儲存，並說明適用邊界。
回答前需要釐清的問題
- 目標是最大數量，還是有權重、優先順序或公平約束？
- n、m、E 的上限是多少，輸入是否已是二分圖且沒有重複邊？
- 只需回傳數量，還是要回傳每組配對及未匹配物件？
- 圖是靜態批次，還是會有增刪邊與線上延遲要求？
30 秒回答框架
「我把兩類物件作為左右頂點，資格關係作為邊。維護 pair_left 與 pair_right，每輪 BFS 從未匹配左點建立只經過匹配邊交替的層次圖，DFS 在層次圖中尋找一組最短增廣路；沿路翻轉邊後匹配數增加。沒有增廣路時由增廣路定理得到最大匹配。複雜度是 O((V+E)√V)，小圖也可以用更簡單的逐點 DFS。」
分步驟深入解答
第一步：建立圖與不變量
只把真實可行的邊放入鄰接表。pair_left[u] 與 pair_right[v] 必須互相指向，或同時為 -1。一次翻轉只改變增廣路上的邊，因此每個頂點仍至多有一條匹配邊。
第二步：BFS 建立層次
從所有未匹配左點同時出發。沿未匹配邊到右點，再沿已匹配邊回到左點，記錄最短層數。只保留能到達未匹配右點的最短層，避免 DFS 在同一輪探索更長的無效路徑。
第三步：DFS 成批增廣
對每個未匹配左點 DFS。訪問到未匹配右點就成功；訪問到已匹配右點時，只遞迴其匹配的左點，並要求層數嚴格增加。每個左點保存目前鄰接游標，失敗後把距離設為無效，避免本輪重複掃描。
第四步：證明終止與正確性
一條增廣路的未匹配邊比匹配邊多一條，沿路異或會讓基數增加一。若 BFS 找不到任何增廣路，增廣路定理說明目前匹配已是最大基數匹配；演算法每輪至少增加一條邊，因此必然終止。
第五步：複雜度與取捨
Hopcroft–Karp 的最壞時間為 O((V+E)√V)，額外空間為 O(V)，圖本身占 O(V+E)。Princeton 的實作還維護最小頂點覆蓋；本題只回傳匹配，不需要那部分。若圖很小，逐個左點 DFS 的實作更短，但最壞可達 O(VE)。加權目標應改用 Hungarian 或最小費用流，不能繼續聲稱本演算法解決它。
可執行的 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高品質示範回答
「先確認目標是最大基數而非加權匹配，並把資格關係作為二分圖邊。兩個配對陣列保證雙向一致。BFS 從全部未匹配左點構造最短增廣路的層次，DFS 用目前邊游標在層次圖裡找盡可能多的點不相交路徑，找到後翻轉路徑邊。沒有增廣路時由增廣路定理結束。實作使用 O((V+E)√V) 時間和 O(V+E) 儲存；若規模小可用簡單 DFS，若有權重則換 Hungarian 或最小費用流。」
常見錯誤
- 把貪心結果叫作最大匹配；極大匹配可能遠小於最大匹配。
- 只保存一側的配對，翻轉增廣路後產生重複占用。
- BFS 找到任意可達路徑就停止，破壞最短層次的批次條件。
- 忘記目前邊游標，DFS 在同一輪反覆掃描失敗邊。
- 把 O((V+E)√V) 誤寫成適用於一般圖、加權匹配或動態更新的保證。
追問及應對
如何生成資格邊而不比較所有 n×m 對？
為標籤建立倒排索引：先把右側物件按標籤分桶，再對每個左物件合併相關桶並去重。邊數仍可能很大，應報告 E、熱門標籤和記憶體預算。
為什麼「沒有增廣路」就能停止？
增廣路每次會讓匹配數增加一；增廣路定理說明存在更大匹配當且僅當存在增廣路。因此 BFS 無法發現它時，目前解已達到最大基數。
如果需求改成帶權偏好怎麼辦？
Hopcroft–Karp 只優化邊數，不能表達權重。可改成 Hungarian 或最小費用最大流，並重新說明複雜度、整數權重範圍和不可行時的降級策略。
圖持續增刪時如何處理？
單機批演算法適合重算。線上場景可從受影響頂點局部尋找增廣路，但要明確延遲、重排次數和暫時非最優的服務契約。