题干与适用场景
例如把题目分配给程序员：左侧是题目，右侧是程序员，边表示至少有一个共同标签。每条边最多选一次，目标是最大化分配数量。PracHub 的公开面经把这类资格分配建模为二分图匹配，并继续追问边生成、分布式协调和流式变更；本题聚焦单机编码部分。
面试官考察点
- 能否区分“任意可行匹配”“极大匹配”和“最大基数匹配”。
- 能否用增广路证明匹配可继续变大，并维护匹配不变量。
- 能否解释 BFS 分层与 DFS 找到一组最短、点不相交的增广路。
- 能否给出 O((V+E)√V) 的最坏时间、O(V+E) 的存储，并说明适用边界。
回答前需要澄清的问题
- 目标是最大数量，还是有权重、优先级或公平约束？
- n、m、E 的上限是多少，输入是否已经是二分图且边无重复？
- 只需返回数量，还是要返回每条配对及未匹配对象？
- 图是静态批处理，还是会有增删边和在线延迟要求？
30 秒回答框架
“我把两类对象作为左右顶点，资格关系作为边。维护 pairleft 和 pairright，每轮 BFS 从未匹配左点建立只经过匹配边交替的层次图，DFS 在层次图中寻找一组最短增广路；沿路翻转边后匹配数增加。没有增广路时由增广路定理得到最大匹配。复杂度是 O((V+E)√V)，小图也可以用更简单的逐点 DFS。”
分步骤深入解答
第一步：建立图与不变量
只把真实可行的边放入邻接表。pairleft[u] 与 pairright[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 或最小费用最大流，并重新说明复杂度、整数权重范围和不可行时的降级策略。
图持续增删时如何处理？
单机批算法适合重算。在线场景可从受影响顶点局部寻找增广路，但要明确延迟、重排次数和暂时非最优的服务契约。