1. 二分图定义

如果一张无向图的 N 个节点（$N >= 2$）可以分成A、B 两个非空集合，其中 $A \cap B = \emptyset$，并且在同一个集合内的点之间没有边相连，那么称这张无向图为二分图。A、B分别称为二分图的左部和右部。

2. 二分图判定

定理：一张无向图是二分图，当且仅当图中不存在奇环。

我们可以根据该定理，使用染色法进行二分图的判定。即刚开始所有点都是没有被染色的，dfs遍历图，如果边的两个点都没有被染色，则指定某个点染色为1， 另一个是2；如果边点两点有一条被染色为 k，则另一个未被染色的边即为 3-k；如果两个点都被染色，如果两个点的染色颜色相同，则该图不是二分图，否则就是二分图。

代码实现如下

bool dfs(int u, int cor) {
    color[u] = cor;
    for(int i=h[u];~i;i=ne[i]) {
        int b = e[i];
        if(!color[b]) {
            dfs(b, 3 - cor);
        } else {
            if(color[b] == cor) return false;
        }
    }
    return true;
}

3. 二分图最大匹配

任意两条边都没有公共端点 的边的集合被称为图的一组匹配。在二分图中，包含边数最多的一组匹配被称为二分图的最大匹配。

那么如何求二分图（无边权）的最大匹配呢？

匈牙利算法：这是一种贪心的思路，实现过程就是遍历所有的左部点，去和右部进行匹配， 对于左部点，遍历其边，如果存在右部点未匹配或者右部点匹配点可以找到其他的左部点， 则匹配成功，否则匹配失败。

具体代码实现如下 ：

bool vis[N * N];
int match[N * N];

bool find(int u) {
  	// 遍历边
    for(int i=h[u];~i;i=ne[i]) {
        int j = e[i];
      	// 如果该点已被指派过，则跳过
        if(vis[j]) continue;
        vis[j] = true;
      	// 如果存在右部点未匹配或者右部点匹配点可以找到其他的左部点
        if(match[j] == -1 || find(match[j])) {
            match[j] = u;
            return true;
        }
    }
    // 匹配失败
    return false;
}

int main() {
		memset(match, -1, sizeof match);
  	int ans = 0;
    for(int i=1;i<=n;i++) {
      	// 清空 vis
        memset(vis, false, sizeof vis);
        if(find(i)) ans ++;
    }
  	return 0;
}

4. 二分图覆盖与独立集

• 二分图最小点覆盖：给定一张二分图，求出一个最小的点集 S，使得图中任意一条边都有至少一个端点属于 S，这个问题被称为二分图的最小点覆盖，简称最小覆盖。

  可以使用Konig 定义证明：

  二分图最小点覆盖包含的点数等于二分图最大匹配包含的边数。

• 二分图最大独立集：任意两点之间没有边相连的点集是独立集，包含点数最多的一个就是图的最大独立集。

  有以下关系：设G是由 n 个节点的二分图，G 的最大独立集的大小等于 n - 最大匹配数。

• 二分图最小路径点覆盖

  有向无环图 G 是的最小路径点覆盖包含的路径条数，等于 n 减去拆点二分图 G2 的最大匹配数。

5. 带权最大匹配 （KM算法）

// TODO

6. 网络流

// TODO

7. 题目集

AcWing 257. 关押罪犯
AcWing 372. 棋盘覆盖
AcWing 376. 机器任务
AcWing 378. 骑士放置
AcWing 379. 捉迷藏