匈牙利算法核心是dfs/bfs找增广路以增广匹配，需正确初始化match[]为-1、每轮重置used[]，通过递归尝试腾位更新match[y]=x；邻接表优于邻接矩阵，注意边方向与下标统一。
匈牙利算法的核心是“找增广路”，不是暴力枚举
直接写个双重循环试图穷举所有匹配，会超时或错解。匈牙利算法本质是 DFS/BFS 在二分图上反复寻找一条能翻转当前匹配状态的路径——即增广路。只要找到一条，匹配数就 +1；找不到，当前匹配就是最大匹配。
常见错误现象：match[y] = -1 初始没设对，导致第一次就跳过有效点；或者 DFS 返回 true 后没更新 match[y] 和 used[x]，结果匹配数卡在 0 或偏小。
- 必须初始化
match[]数组为 -1（表示未匹配），不能用 0 - 每次 DFS 前重置
used[]（仅限当前轮次的左部点访问标记） - DFS 函数返回
bool：找到增广路就返回 true，并在回溯中更新match[y]和match[x]
DFS 版匈牙利算法模板要避开递归栈溢出和重复访问
当左部点数量大（比如 1e4）、图又稠密时，纯递归 DFS 容易爆栈或 TLE。关键不是“写得短”，而是控制访问边界和剪枝逻辑。
使用场景：稀疏二分图、左部点 ≤ 5000、需要代码简洁可读；不适用于左部点带权或要求字典序最小匹配。
立即学习“C++免费学习笔记（深入）”；
bool dfs(int x) {
for (int y : graph[x]) {
if (used[y]) continue;
used[y] = true;
if (match[y] == -1 || dfs(match[y])) {
match[y] = x;
return true;
}
}
return false;
}
-
used[y]是右部点标记，每轮 DFS 前 memset 为 false，不能复用上一轮 -
match[y] == -1是终止条件之一，代表 y 尚未匹配，可直接占用 - 递归调用
dfs(match[y])是关键：尝试把原来匹配 y 的左部点match[y]“腾”出来，给 x 让位
邻接表 vs 邻接矩阵：图存法直接影响性能和内存
邻接矩阵（vector<vector>> g</vector>）看似直观，但空间 O(V²)，且遍历每个右部点都要扫满列，实际复杂度接近 O(n³)。邻接表才是标配。
参数差异：graph[x] 存的是所有与左部点 x 相连的右部点编号（从 0 开始或 1 开始需统一），不是边权也不是是否可达。
- 右部点总数记作
m，左部点总数记作n，数组match长度应为m，下标对应右部点编号 - 若输入是 1-indexed 边（如
u v表示左部 u 连右部 v），存图时记得graph[u-1].push_back(v-1) - 不要在 DFS 里反复调用
graph[x].size()，提前存进变量避免多次计算
匹配失败时 debug 要看三处：match 初始化、used 复位、图边方向
最常被忽略的是边方向反了——把右部点当成起点去连左部点，或者误以为 match[x] 存左部匹配，其实标准写法里 match[y] 才存右部点 y 匹配的左部点 x。
错误信息典型表现：match[y] 始终为 -1（图没建对）、dfs() 永远返回 false（used 没清或初始值错）、程序运行后匹配数为 0（左部点编号越界导致图没存进去）。
- 打印前几条边验证
graph[0]是否非空，确认建图成功 - 检查
match数组长度是否等于右部点总数，下标是否越界 - 确保
used数组大小 ≥ 右部点总数，且每次调用dfs前用memset(used, 0, sizeof used)或fill
