匈牙利算法的核心是不断寻找增广路径，每找到一条即可使匹配数加1；其本质是从未匹配左部点出发的交替路径，通过翻转路径上边的匹配状态来扩展匹配。
匈牙利算法的核心是不断找增广路
它不直接“算匹配数”，而是通过反复尝试给未匹配左部点找一条能翻转边状态的路径（增广路），每找到一条，匹配数就+1。关键在于：每次 DFS 或 BFS 从一个未匹配的左部节点出发，只走“未匹配→已匹配→未匹配…”交替的边，且右部节点不能重复访问。
常见错误是没重置 visited 数组——每次从新左部点开始找增广路时，必须清空右部节点的访问标记；否则会漏掉本可扩展的路径。
- 左部点集合记为
U，右部点集合记为V，邻接关系用graph[u]存储 u 能连到的 v 的列表 - 用
matchV[v]记录右部点 v 当前匹配的左部点（-1 表示未匹配） - 用
matchU[u]记录左部点 u 当前匹配的右部点（-1 表示未匹配），可选，但查起来快 - DFS 函数返回
bool：是否成功为当前u找到增广路
DFS 实现里怎么写递归逻辑
对当前左部点 u，遍历所有邻接右部点 v，若 v 未被本轮访问过，就标记并尝试：如果 v 没匹配，或 v 已匹配但其原配 matchV[v] 能腾出位置（即递归调用成功），就把 u 和 v 配上。
bool dfs(int u, const vector<vector<int>>& graph, vector<int>& matchV, vector<bool>& visited) {
for (int v : graph[u]) {
if (visited[v]) continue;
visited[v] = true;
if (matchV[v] == -1 || dfs(matchV[v], graph, matchV, visited)) {
matchV[v] = u;
return true;
}
}
return false;
}注意：递归调用传的是 matchV[v]（即 v 原来的左部搭档），不是 u；这是让原配去另找对象，把位置“让”出来。
立即学习“C++免费学习笔记（深入）”；
性能上，最坏时间复杂度是 O(V * E)，其中 V 是左部点数，E 是边数；实际中远快于理论值，尤其图稀疏时。
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
主循环为什么必须对每个左部点单独跑 DFS
因为增广路起点只能是未匹配左部点；已匹配的点不能作为起点（否则路径不合法）。所以主逻辑是：
- 初始化
matchV全为 -1 - 对每个
uin [0, |U|)，新建visited（大小等于 |V|，全 false） - 调用
dfs(u, ...)，若返回 true，匹配数加 1
容易忽略的坑：visited 必须在每次 dfs() 调用前重置，不能在整个算法外只建一次——不同 u 的搜索空间独立，混用会导致误判“某 v 已访问过”而跳过可行分支。
建图和边界处理要注意什么
输入如果是 1-indexed 的点编号，务必减 1 再存入 graph；右部点索引也必须从 0 开始，否则 matchV[v] 会越界。若右部点总数未知，可在读边时记录最大 v 值，或直接用 vector<int>(maxV + 1, -1) 初始化。
没有自环、无向边要双向存吗？不用——二分图匹配只存左→右的有向边即可，graph[u] 只需包含 u 能连的 v；反向边由 matchV 隐式提供。
如果运行结果比预期小，先检查：图是否真为二分图（可用染色法验证）、matchV 大小是否够、DFS 中 visited 是否真的每次重置、以及递归出口条件是否写反（比如写成 != -1 而非 == -1）。
真正卡住的地方往往不在算法主干，而在建图索引错位或访问数组复用——多打两行 cout << u << " tries " << v << endl; 就能快速定位哪条边根本没走到。
