参考：外层循环为什么正确

读者问答整理：为什么 dfs(u) 开始时 u 一定未匹配，成功路径必是增广路，失败的左部点为何终身没有机会。

  • 二分图
  • 匈牙利算法
  • 匹配
  • 图论

算法主体见：匈牙利算法。本文整理一个关于主循环的提问和完整回答，讨论这段代码的正确性：

cpp 
        
1
2
3
4

        for (int u = 1; u <= n; u++) {
    fill(vis.begin(), vis.end(), 0);
    if (dfs(u)) ans++;
}

记号与正文一致：match[v] 表示右部点 vv 当前匹配的左部点，0 表示空闲；vis[v] 是本轮搜索的访问标记。

提问

外层循环执行到 uu 时，1,2,…,u−11,2,\ldots,u-1 都已经 dfs 过了。那么 uu 在第一层 dfs 时，是不是一定从未匹配点出发？

1. 到达 u 时前面的都搜索过了，但不一定都匹配上了

外层循环按 1,2,…,n1,2,\ldots,n 逐个发起搜索，到 uu 时前面的确实都处理完了。但注意：dfs 过不等于都匹配上了。例如通过数据理解 dfs 过程例一第 3 轮的 u3u_3 就失败了，它一直处于未匹配状态。

2. dfs(u) 开始时，u 一定未匹配

结论成立，理由要记牢：看递归能"够到"谁。

  • 新左部点被匹配的唯一机会，是自己这一轮走成功分支 match[v] = u；
  • 递归入口 dfs(match[v]) 要求 match[v] != 0，也就是说递归只会进入已经匹配的左部点；
  • 所以任何时刻，已匹配的左部点集合都是已处理过的 {1,…,u−1}\{1,\ldots,u-1\} 的子集。

uu 自己这轮还没执行，又不可能被别人的递归提前匹配，所以站在第一层的 uu 必然未匹配。

3. 成功时找到的一定是增广路

dfs(u) 成功意味着走到了 match[v] == 0 的出口，整条路径形如：

u⏟未匹配左部点→v1→u1→v2→⋯→vk⏟未匹配右部点（出口） \underbrace{u}_{\text{未匹配左部点}} \to v_1 \to u_1 \to v_2 \to \cdots \to \underbrace{v_k}_{\text{未匹配右部点（出口）}}

首尾都是未匹配点，匹配边与非匹配边交替出现，这正是增广路的定义。回溯时逐层改写 match 就是沿着这条路翻转边的匹配状态，匹配数增加 11，所以 ans++ 是准确的。

4. 失败的 u 终身没有机会

uu 这轮失败后，后面的轮次还会修改匹配，uu 会不会又有机会？不会：

  • 失败说明 uu 沿交替路能到达的右部点全部有人占，且占位者全都挪不动（他们的候选也全在这个圈内）；
  • 后续增广只会让已占的右部点换主人，已占的右部点永远不会变空（增广路终点吃掉的是空闲点，中间点换人并不腾空）；
  • 所以这个封闭圈永远解不开，uu 保持未匹配直到结束。这也说明前面失败的点不需要在后续轮次中重试。

用集合语言说：记 SS 为第 uu 轮中 vis 标记过的右部点集合。失败意味着 SS 是封闭的——占位者的邻接表全部落在 SS 内。后续任何增广路都无法穿过 SS 并到达空闲右部点（进了 SS 就出不来，也走不到终点），因此 SS 内的占位关系永远不会被打断。

小结

  1. 每轮的起点 uu 一定未匹配，成功走出的路径一定是增广路，匹配数正确地加一；
  2. 已匹配的左部点只会换右部点、不会丢匹配，匹配数单调不减；
  3. 失败的左部点永久失败，无需重试；
  4. 结束时不存在从任何未匹配左部点出发的增广路，由增广路定理（无增广路即最大匹配）知算法正确。