##概念
二分图： 又称作二部图，是图论中的一种特殊模型。 设G=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集(A,B)，并且图中的每条边（i，j）所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B)，则称图G为一个二分图。
无向图G为二分图的充分必要条件是，G至少有两个顶点，且其所有回路的长度均为偶数。
最大匹配：图中包含边数最多的匹配称为图的最大匹配
##介绍
求最大匹配，匈牙利算法
算法的思路是不停的找增广路径, 并增加匹配的个数,增广路径顾名思义是指一条可以使匹配数变多的路径，在匹配问题中,增广路径的表现形式是一条”交错路径”，也就是说这条由图的边组成的路径， 它的第一条边是目前还没有参与匹配的，第二条边参与了匹配，第三条边没有..最后一条边没有参与匹配，并且始点和终点还没有被选择过。这样交错进行，显然他有奇数条边。那么对于这样一条路径，我们可以将第一条边改为已匹配，第二条边改为未匹配…以此类推。也就是将所有的边进行”反色”，容易发现这样修改以后，匹配仍然是合法的，但是匹配数增加了一对。另外，单独的一条连接两个未匹配点的边显然也是交错路径。可以证明。当不能再找到增广路径时，就得到了一个最大匹配，这也就是匈牙利算法的思路。
##应用
OJ参考题目：poj1469 poj2446 poj2819
##模板1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33//注意：结点标号从1开始！
//u1 -- v1
//u2 -- v2
bool gh[][] //graph that if two points is connected
bool b[] //if b[v] is used
int link[] //link[v] = u
bool Find(int u){
for (int v = 1; v <= (v); v++){
if (gh[u][v] && !b[v]){
b[v] = true;
//如果结点标号从0开始,可以使用 link[v] == -1
if (link[v] == 0 || Find(link[v])){
link[v] = u;
return true;
}
}
}
return false;
}
int main(){
int ans = 0;
for (int i = 1; i <= (u); i++){
memset(b, 0, sizeof(b));
if (Find(i)) ans++;
}
//ans为边的匹配数
}