056-图论-DFS匹配

用 DFS 在二分图上寻找增广路以逐步扩大匹配，适用于实现简单、规模中小或作为基线方案的场景。

Description: Simple bipartite matching algorithm. Graph $g$ should be a list of neighbors of the left partition, and $btoa$ should be a vector full of -1’s of the same size as the right partition. Returns the size of the matching. $btoa[i]$ will be the match for vertex $i$ on the right side, or $-1$ if it’s not matched. Time: O(VE)

• 定义与背景

  • 问题：给定二分图 G=(L∪R,E)，求最大匹配 M，使任意边两端顶点不共享。
  • 状态表示：
    • 图结构 g：仅需存左部 L 的邻接表 g[u]⊆R。
    • 匹配数组 btoa：|R| 长度，btoa[v]=u 表示右点 v 匹配到左点 u，未匹配为 -1。
  • 适用：当无需亚线性/更快的渐进复杂度、实现需极简、或作为对拍/基线时。

• 接口/数据结构（据实现习惯）

  • g: vector，左侧每个顶点 u 的邻接右侧点集。
  • btoa: vi，右侧匹配；初始化为 -1。
  • vis: vi/bitset，每次“从某个左点出发的尝试”过程中用于右点访问标记（或对左点标记，二者皆可，但需自洽）。
  • 返回值：整型，匹配边数。

• 核心流程/要点（DFS 增广）

  1. 初始化
     • btoa 全置 -1；答案 match=0。
  2. 对每个左点 u∈L 执行一次“找增广路”的尝试：
     • 清空本次 vis 标记；
     • 调用 dfs(u)：遍历 u 的所有邻接右点 v；
       • 若 v 未匹配（btoa[v]==-1），或其当前匹配到的左点 u’ 能通过递归 dfs(u’) 让出另一条边，则可将 btoa[v]=u 并返回 true；
       • 否则继续尝试下一个 v。
     • 若 dfs(u) 成功，match++。
  3. 结束条件
     • 所有左点尝试完毕；或某些实现会在一轮中未增加匹配时提前结束（但经典版本仍对每个 u 尝试一次）。
  4. 访问标记复用策略
     • 常见做法：在“从某个左点 u 的一次 dfs(u)”中，对右点 v 使用 vis[v] 防回溯与重复探索；
     • 也可对左点使用时间戳式标记避免重复递归；关键是“每次左点发起的搜索”需有独立的访问状态。
  5. 正确性直觉
     • 每次成功的 dfs(u) 都找到一条从未匹配左点到未匹配右点的增广路，沿路交替翻转匹配/非匹配边，使匹配大小+1；
     • 若不存在增广路，则当前匹配为极大；在二分图上，增广路存在性与非最优性等价。

• 复杂度与边界条件

  • 时间复杂度：一次 dfs 最坏 O(E)，对每个左点尝试一次，总计 O(VE)（V=|L|+|R|）。
  • 空间复杂度：O(V+E)。
  • 多源/不可达：对不连通部分自然处理；不可达右点永不会被匹配。
  • 重边/自环：重边可能造成重复尝试但不破坏正确性；二分图语境下自环应预过滤。
  • 图规模与类型：
    • 顶点数中等（数万）+ 稀疏边通常可接受；
    • 对极大规模或高密度图，建议使用 067-图论-HopcroftKarp 以降到 O(√V·E)。
  • 哨兵与初始化：btoa 用 -1 作未匹配哨兵；vis 刷新频率与作用域需与 dfs 尝试严格一致。

• 变体/扩展

  • Hopcroft–Karp：按层分组批量增广，复杂度 O(√V·E)，对大图显著更快，接口与本法相近（参见 067-图论-HopcroftKarp）。
  • 用最大流求匹配：将二分图构造成 s→L→R→t 的网络，容量为 1，使用 057-图论-Dinic最大流 或 060-图论-EdmondsKarp；便于统一到“流/割”框架，代价是常数较大。
  • 带权匹配：本法仅解“最大基数匹配”；若需带权（最大权/最小权），需改用带权匹配算法（参见 079-图论-带权匹配）。
  • 在线/动态匹配：需要支持新增边或顶点时，需维护可更新的数据结构；本法可作基线或每次重跑。

• 正确性要点与不变式

  • 增广不变式：每次增广将匹配数恰增 1，且匹配的“边不共享端点”性质保持不变。
  • 访问控制：在一次 dfs 尝试中，任一右点至多被访问一次，保证递归终止与复杂度上界。
  • 极大=最大（在有增广路当且仅当非最优）：无增广路时当前匹配即为最大匹配。

• 与相邻技术对比与取舍建议

  • 与 Hopcroft–Karp：HK 在大图更优；DFS 匹配代码短小，适合快速实现、调试与作为对拍基线。
  • 与最大流（Dinic/Edmonds–Karp）：流方法通用性强，可顺带得到最小割等信息；若仅做二分匹配且数据大，HK 更高效。
  • 与“一般图匹配”对比：DFS/HK 针对二分图；一般图需 Blossom 等更复杂算法（参见 063-图论-一般图匹配）。

关联节点

• 057-图论-Dinic最大流
• 067-图论-HopcroftKarp
• 079-图论-带权匹配