二分图的概念
二分图又称作二部图，是图论中的一种特殊模型。假设 \(G=(V,E)\) 是一个无向图，如果顶点 \(V\) 能够分割为两个互不相交的子集 \((S,T)\)，并且图中的每条边 \((s,t)\) 所关联的两个顶点 \(a\) 和 \(b\)，分别属于这两个不同的顶点集 \((s \in S,t \in T)\)，则称图 \(G\) 为一个二分图。
如何判定二分图
通过BFS染色法，我们能够快速判定一个图是不是二分图。我们随便选择一个顶点出发，将其染为白色，从这个顶点出发将其邻接的顶点全部染成黑色，然后再从黑色的顶点出发，将其邻接未访问的顶点染为白色，如此反复即可。上述的过程出现了三种状态，「未访问」、「白色」与「黑色」，我们可以使用一个数字 \(state\)，然后分别使用 \(0、1、2\) 三字数字表示三种不同的状态。这个过程也能使用 DFS 实现。
最大二分图匹配算法
HA算法
二分图最大匹配是指，给定一个分为左右两个部分的二分图，两个部分内部的顶点连边，现在要求选出跨两个部分的连边(没有公共顶点的连边)，并且连边的数量最大。简单来说，我们可以想象这样一个相亲模型，左边是男孩，右边是女孩，我们的身份就是月老，我们要做的事情是令左右两边的男生与女生凑出对数最大。
左右两边匈牙利算法 (HA算法) 主要用于无权图，匈牙利算法也称 KM 算法，KM 其实是作者名字的缩写，其基于匈牙利算法改进得到的。匈牙利算法的运行流程非常简单，我们首先遍历集合 \(S\) 或 \(T\) 任意一个，我们不妨先从左边的、代表男生的集合出发，然后枚举这个男生感兴趣的所有女生。
例如 \(A\) 感兴趣的女生包括了 \(E、G、H\)，我们规定访枚举的顺序是自上而下的，那么访问女生 \(E\)，如果女生 \(E\) 也未匹配，那么我们则令\((A,E)\)构成一个配对，然后更新匹配数量。我们可以使用一个数组 \(match\) 记录当前的配对情况的。然后轮男生 \(B\)，其感兴趣的女生的只有 \(E\)，但是 \(E\) 已经匹配了，于是我们尝试令与\(E\)匹配的 \(A\) 更换匹配对象。显然，由于 \(A\) 感兴趣的女生除了\(E\) 之外仍有 \(G,H\)，那么 \(A\) 不选 \(E\)，改选 \(G\) 便可君子成人之美的腾出 \(E\)，使得 \((B,E)\) 构成一个匹配。当前拥有的匹配包括 \((A,G)、(B,E)\)，然后轮到了男生 \(C\)，其感兴趣的只有 \(F\)，且未被匹配，那么构成匹配 \((C,F)\)，然后轮到了男生 \(D\)，很不巧，其喜欢的女生 \(G\) 已与 \(A\) 匹配，因而我们再一次令 \(A\) 更换对象，\(A\) 除了 \(E,G\) 之外仍对 \(H\) 感兴趣，因而 \(G\) 最终让给 \(D\), \(A\) 选择 \(H\)，那么最终我们得到了四对匹配。
int find(int u){
for (int v: edges[u]){
if(!vist[v]){
vist[v] = 1;
if(!match[v] || find(match[v])){
match[v] = u;
return true;
}
}
}
return false;
}
基于DFS实现的匈牙利算法，其实非常简洁，选择\(S\)或\(T\)其中一个集合开始的遍历，进入一个未访问的顶点，如果没有匹配，令其匹配，如果已经匹配，尝试令其匹配对象更换对象，腾出空位。然而如果二分图较大，尝试「更换匹配，腾出空位」这个过程的递归深度有可能会非常之深，寻找替代对象的搜索路径会在 \(S\)、\(T\)两个集合之间反复交错。