最近图论各种跪，于是终于下决心开一个系列来梳理总结一下所学的各种图论算法。
定义
首先通过简单的例子来引入二分图的定义。假如我们有一群男生和女生，任意一对男女之间都可以建立暧昧关系。这样我们可以将所有男女作为分属两个集合中的点，一对男女分属两个集合，可以建立关系；但是两个在同一集合中的男生或者女生就不能建立关系，因为他们中没有搞基或者搞LES的。这样的一群男女以及他们的暧昧关系就构成一个二分图。也就是说，对于任意一个图G = (V, E)，如果我们能够将它的点集V划分为这样的两个点集V1和V2，使得边集E中所有边的两端点一定分属两个点集，那么称这个图为二分图。
图论中，一个「匹配」（matching）是指一个边的集合，其中任意两条边都没有公共顶点。还是以上述例子来说明，同一个男生（或者女生）可以有多个暧昧对象，但是只能和一个异性建立恋爱关系。这样这群男女中所能够产生的恋爱关系，称为他们的一个“匹配”。所谓二分图的最大匹配，就是指边数最多的匹配，对应到上述例子中就是指所能够产生的最多对情侣。所以我们可以感受到，“匹配”这个翻译还是非常形象的，它就是指节点“一对一”的对应关系。
判定
无向二分图本质上就是一种不存在奇数环的图，使用染色法就可以进行快速判定。方法是首先随意选取一个未染色的点进行染色，然后尝试将其相邻的点染成相反的颜色。如果邻接点已经被染色并且现有的染色与它应该被染的颜色不同，那么就说明不是二分图。而如果全部顺利染色完毕，则说明是二分图。染色结束后的情况（记录在数组中）便将图中的所有节点分为了两个部分，即为二分图的两个点集。
最大匹配
求解二分图最大匹配问题的一个算法是匈牙利算法，为了进行解释，首先引入两个定义：
交替路：从一个未匹配点出发，依次经过非匹配边、匹配边、非匹配边...形成的路径叫交替路。
增广路：从一个未匹配点出发，并且以一个未匹配点结束的交替路称为增广路。
增广路有一个重要性质：路径上的非匹配边比匹配边多一条。因此，为了改进现有匹配以获得更大的匹配，我们只需要找出一条合法的增广路，并把增广路中的匹配边和非匹配边的身份交换即可。由于中间的匹配节点不存在其他相连的匹配边，所以这样做不会破坏匹配的性质。交换后，图中的匹配边数目就会比原来增加1条，也就是完成了一次改进。重复这样的过程，直到找不到一条增广路为止，此时得到的匹配即为二分图的最大匹配。寻找增广路的算法使用DFS实现出来极其简洁优雅，函数DFS()返回由某一未匹配节点开始的路径是否为增广路。按照惯例，代码贴在文章的末尾。
下面先以一个简单图为例来演示一下算法的整个流程，最好对照着代码实现来看。首先我们有一个由6个节点组成的二分图，上下各有三个节点以如图所示方式连接，我们分别称之为“上1-3点”和“下1-3点”。我们约定建图时的加边顺序为从上三个节点向下三个节点连有向边；约定以Match数组记录其中下三点所对应的匹配点，这样如果Match中某个节点的值为undefined，说明这个节点还未被匹配。那么问题来了，为什么我们只从一个点集（也就是上侧）开始DFS？为什么我们研究的是无向二分图的最大匹配，但在这里加的却是有向边，只从一侧连向另外一侧？为什么上下节点的编号可以相同却不影响结果？这两个问题将在下文给出分析。
按照代码示例中的算法，我们要遍历上侧点集进行DFS寻找增广路。首先我们从上1节点进行DFS，走到了下1节点，此时下1节点的Match[1]为undefined，说明这两个点可以匹配，于是记录Match[1] = 1并返回True，此时DFS就结束了，总匹配数为1。
同理，从上2节点进行DFS，记录Match[2] = 2后返回，总匹配数加1后为2。
下面就到了匈牙利算法的核心部分，寻找增广路并进行增广的过程：
首先我们可以看到，从上3节点进行DFS，第一次走到了下2节点。显然这个节点被红边所连接，是一个已匹配点，于是就从下2节点所对应的匹配节点——上2节点开始DFS。从上2节点进行DFS时，由于下2节点已经访问过不能再走，所以就走到了下1节点。下1节点仍然是已匹配点，于是从它的对应点上1节点再进行DFS。又因为下1节点已经访问过，所以此次从上1节点的DFS只能走到下3节点。终于，下3节点是一个未匹配点，我们找到了一条增广路，返回True之后总匹配数加1变成了3，即为这个图的最大匹配。
将匹配边与非匹配边交换的代码实现非常简单，在回溯的过程中加一句Match[v] = u即可。这样做的合法性在于，这句代码第一次执行是在找到了增广路的结束点，即未配对点时，然后会不断回溯更新。在这个例子中，我们总共进行了三次递归调用，即在递归终点处存在一个三层的函数调用栈。当DFS走到下3节点时确定找到了一条增广路，这时在调用栈顶，于是将未配对的下3节点与上1节点配对（因为是从上1节点DFS过来的）；然后回溯并退栈一层之后，由于上1节点是从下1节点的配对点Match[1]执行DFS(Match[v])来调用的，所以函数调用栈中u为2而v为1，下1节点会与上2节点配对；同理，下2节点会与上3节点配对。这样最终得到的最大匹配就如下所示了：
通过上述过程我们可以看出，只需要用一个Match数组就可以记录下层节点对应上层节点的匹配关系。并且只要调用DFS寻找增广路时是以上层节点编号作为参数，那么每次递归调用时传递的参数就都是指上层节点的编号，也就是说遍历边时只存在由上层节点走向下层节点的走法。因此判断点能不能走的时候也只需要判断下层节点是不是走过（是否已经加入了增广路）即可。由对称性可知，如果选择从下层节点出发寻找增广路，那么每次函数调用只会以下层节点的编号作为参数，情况是一样的。
这样梳理整个流程后，我们就回答了上述的问题：增广路是对称的——以未覆盖点开始，同样以未覆盖点结束；如果我们从一侧未覆盖点进行DFS时找不到增广路，那么从另外一侧再DFS当然也一样找不到。由于在DFS寻找增广路的过程中只用到了从一个点集走向另外一个点集的边，因此单向加有向边即可。双向加边当然也可以，不过这样就相当于求了两次最大匹配，结果应该除以2。而当我们不需要输出具体的匹配方案，只需要输出最大匹配数时，两个点集中节点的编号完全可以存在重合，因为每次DFS调用时的参数（节点编号）都只是属于其中一个点集的。这样做会带来一个好处：每次DFS求增广路前必须清空标记数组，如果节点编号重合，就可以减小这个开销，数组可以减少一半的大小。
代码示例
HDU 2444 （二分图判定+最大匹配数）
const int MAX = 210;
//vector存储邻接表
VI Adja[MAX];
//保存节点的染色情况
int color[MAX];
//保存节点的匹配节点，以及某个节点是否被加入了增广路
int match[MAX], visited[MAX];
//点数、边数
int n, m;
//二分图判定
bool judge( int u, int prev )
{
if ( color[u] != 0 ) {
if ( color[u] != -prev ) return false;
else return true;
}
color[u] = -prev;
rep(i, Adja[u].size()) {
if ( !judge(Adja[u][i], color[u]) )
return false;
}
return true;
}
//初始化
void Init()
{
CLR(color, 0);
rep(i, n + 1) Adja[i].clear();
}
//数据读入
void Read()
{
int a, b;
rep(i, m) {
scanf("%d %d", &a, &b);
Adja[a].PB(b);
Adja[b].PB(a);
}
}
//DFS寻找增广路
bool DFS( int u )
{
rep(i, Adja[u].size())
{
//枚举与点u相邻的所有点（邻接表存储）
int v = Adja[u][i];
//如果在本次DFS中未被访问过，即不在交替路上
if ( !visited[v] )
{
visited[v] = true;
//如果是未匹配点，就可以结束并返回true
//如果从这个点继续DFS可以找到未匹配点，则DFS后返回true
if ( match[v] == -1 || DFS( match[v] ) )
{
match[v] = u;
return true;
}
}
}
//若找不到交替路，则返回false
return false;
}
//二分图匹配
int Hungary()
{
int res = 0;
CLR(match, -1);
REP(u, 1, n + 1)
{
//清空标记数组
CLR( visited, 0 );
if ( DFS(u) ) res++;
}
return res;
}
int main()
{
//std::ios::sync_with_stdio(false);
while ( scanf("%d %d", &n, &m) != EOF )
{
Init();
Read();
if ( !judge(1, 1) ) {
puts("No");
} else {
int res = Hungary();
printf("%d\n", res / 2);
}
}
}