二分图

二分图：设 $G$ 是一个无向图，若它的顶点集合 $V$ 可以被分割为两个互不相交的子集 $V_{1}, V_{2}$ ，而图中的每条边 $e \in E$ 的顶点 $(u, v) = e$ 都分属于这两个不同的子集，即 $u \in V_{1}, v \in V_{2}$ ，那么称图 $G$ 为 二分图。

染色法可以用来判别一个图是否为二分图，思想是 DFS，时间复杂度为 $O (n + m)$ 。

一个图是二分图当且仅当图中不含奇数环：

显然，二分图的环，起点和 终点前一个点 分属不同子集，矛盾！
若一个图不含奇数环，任取一个顶点，根据这个顶点到其他顶点的最短距离的 奇偶性 分组构造即可
因此也可以按照顶点到其他顶点最短距离的奇偶性进行 二染色

算法：依次遍历所有顶点，只要 i 没有染色，将它连通块的所有顶点进行二染色（深度优先遍历）。

AC860. 染色法判定二分图

核心代码：

cpp

bool dfs(int u, int c) {
    color[u] = c;

    for (int i = h[u]; i != -1; i = ne[i]) {
        int j = e[i];
        if (!color[j]) {
            if (!dfs(j, 3 - c)) {
                return false;
            }
        }
        else if (color[j] == c) {
            return false;
        }
    }

    return true;
}

这里的 dfs() 返回 true 表示该点及其连通块中所有点染色成功
对于点 u 的所有邻接表上的直接关联的点，都染色成 3 - c，1 染成 2，2 染成 1
- 如果 j 尚未染色，深度优先搜索下去，只有后面节点中出现 false 才会终止操作
- 这里直接 return dfs(j, 3 - c); 不可以
- 如果 j 已经染色，且染的颜色和 u 相同，直接返回 false
- 如果 j 已经染色，且染的颜色和 u 不同，跳过

AC257. 关押罪犯

二分图 ​

二分图