二分图的最大匹配

图的匹配是指任意两条边都没有公共端点，也就是顶点只能一一配对（可能有顶点孤立，但是不能一配多）

如果路径上匹配边和非匹配边交替出现，且首尾是非匹配边，则称此路径为增广路，将增广路上的边的匹配状态取反后，仍然是一组匹配，并且匹配数增加1

最大匹配等价于不存在增广路（若有增广路，匹配数还能加1），可用匈牙利算法寻找增广路来计算二分图的最大匹配

存储结构采用邻接链表，二分图分为A、B两部分，把无向图存成有向图，只存储A指向B的边即可，n1、n2为A、B顶点数，m为A指向B边数

int value[m], next[m], head[n1], d;

memset(head, -1, sizeof(head));

match[j]标示B中顶点j所匹配的A中顶点编号，初始化为全-1表示尚未匹配，vis[j]标示B中顶点j是否在当前递归的增广路中（0为不在，1为在）

int match[n2], vis[n2];

算法采用深度优先遍历实现，尝试寻找A中顶点x在B中的匹配，遍历x所有邻接顶点y，如果y尚未匹配或者y已匹配但可以找到增广路，则匹配成功

（<x, y>是非匹配边，<y, match[y]>是匹配边，依次类推直到找到尚未匹配的B中顶点，递归形成的就是一条增广路，回溯时将匹配状态取反）

（一个顶点不能在增广路中出现两次，否则递归无法终止，故而需要vis数组）

bool find(int x) {
    for (int i = head[x]; i != -1; i = next[i]) {
        int y = value[i];
        if (!vis[y]) {
            vis[y] = 1;
            if (!match[y] || find(match[y])) {
                match[y] = x;
                return true;
            }
        }
    }
    return false;
}

遍历A中所有顶点，统计匹配数量，寻找A中每个顶点的匹配前都要将vis数组初始化为全0

int cnt = 0;
for (int i = 0; i < n1; i++) {
    memset(vis, 0, sizeof(vis));
    if (find(i)) cnt++;
}

注解：A和B中顶点编号是独立的，可以有顶点是相同编号

---