二分图是一种特殊的图结构。

如果图 G 可以划分成两个点集 $V_1,V_2$ 使得两个点集内部不存在边，则图 G 是一个二分图。

判定

图 G 是 2- 着色的 $\iff$ 图 G 是二分图。

容易证明，将点属于的集合 $V_i$ 作为点的颜色，那么二分图相邻点一定是不同的。

dfs 朴素染色即可，若出现相邻节点颜色相同则图不是二分图，因为每个点只会被染一次，所以时间复杂度：$O(n)$。

bool dfs(int x, int c) {
    col[x] = c;
    for (auto u : p[x]) {
        if (!col[u]) {
            if (!dfs(u, 3 - c))
                return 0;
        } else if (col[u] == c)
            return 0;
    }
    return 1;
}
for (int i = 1; i <= n; i++) {
    if (!col[i]) {
        if (!dfs(i, 1)) {
            cout << "No\n";
            return;
        }
    }
}

图 G 中不存在奇环 $\iff$ 图 G 是二分图。

容易发现，奇环无法二染色，偶环可以二染色，环只有奇环和偶环，去掉环后，图是一棵树，树一定可以二染色。

考虑怎么在图上表示一个环，建出图的 dfs 生成树（容易发现二分图在各个连通块之间独立，所以这里仅考虑一个连通块）那么环就是树上一条路径加一条若干条非树边。

若将仅一条非树边形成环定义成“基环”。

那么容易发现，一般环可以在 dfs 生成树上对应成若干基环。

若每一个基环都是偶环，那么形成的每一个生成环，也都是偶环。

所以只要判掉是否存在一个奇长的基环即可。树上链长可以使用节点深度作差得到。

时间复杂度：$O(n)$。

// 维护 dfs 生成树
for (int i = 1; i <= n; i++) {
    for (auto u : p[i]) {
        if (u != fa[i] || fa[u] != i) {
            if ((dep[u] & 1) == (dep[i] & 1)) {
                // 存在奇环
                return;
            }
        }
    }
}

扩展域并查集判二分图

从二分图定义出发，点集需要能被划分成两个集合。

那么对于一条边 $(u,v)$ 就表示了 $u$ 和 $v$ 不能在同一个集合中。

使用扩展域并查集维护即可。

时间复杂度：$O(n\alpha (n))$。

for (auto [u, v] : edge) {
    if (dsu.same(u, v) || dsu.same(u + n, v + n)) {
        // 不能划分到两个集合中
        return;
    }
    dsu.merge(u, v + n);
    dsu.merge(u + n, v);
}

使用扩展域并查集可以在线判断二分图。

应用

基于二分图的特殊性质，一些在一般图上比较困难的问题会变得相对容易。

1. 二分图最大匹配

匹配指一组边，图中每个点只出现在其中一条边中。

最大匹配指要求选出最多边。

求解：

一般情况下，使用匈牙利算法即可求二分图的最大匹配，时间复杂度：$O(nm)$。

注：极端情况下，二分图使用网络流算法 Dinic 求最大流，时间复杂度为 $O(m\sqrt{n})$。

构造：

匈牙利算法可得最大匹配的一种可行方案。

2. 二分图最小点覆盖

最小点覆盖问题是指，在一张无向图中选择最少的顶点，满足每条边至少有一个端点被选。

求解：

一般图的最小点覆盖问题是 NP-hard 的，在二分图上，最小点覆盖 $=$ 最大匹配。

构造：

和最大匹配相同，选择最大匹配的每条边的一个顶点即可。

3.二分图最大独立集

最大独立集问题是指，在一张无向图中选择最多的顶点，满足两两之间互不相邻。

求解：

最大独立集问题对于一般图是 NP-hard 的，在二分图上，最大独立集 $=$ 顶点数 $-$ 最小点覆盖。

构造：

取最小点覆盖补集。

4.有向无环图最小路径覆盖

最小路径覆盖问题是指，在一张有向图中，选择最少数量的简单路径，使得所有顶点都恰好出现在一条路径中。

一般的有向图上的最小路径覆盖问题是 NP-hard 的。

求解：

DAG 的最小路径覆盖 $=$ 顶点数量 $-$ 相应的二分图 $G^{\prime }=(V^{\text{in}},V^{\text{out}},E^{\prime })$ 的最大匹配。

构造：

5.有向无环图最小路径重复点覆盖

最小路径覆盖问题是指，在一张有向图中，选择最少数量的简单路径，覆盖所有点，点可以出现在多条路径上。

求解：

记原图 $G$，求传递闭包后的图 $G^{\prime }$，则 $G$ 的最小路径重复点覆盖 $=G^{\prime }$ 的最小路径覆盖

一个简单转换：在 DAG 中，若 $i$ 可达 $j$，那么建边 $i,j$。对此图求最大匹配 $c$，那么原 DAG 的最小路径覆盖就是 $n-c$。

DAG 上可达是 $O(\frac{n^2}{w})$ 求解的，一般不劣于求解最大匹配。

构造：

6. 二分图最大权匹配

二分图的最大权匹配是指二分图中边权和最大的匹配（相应地，最大匹配相当于边权为 $1$ 的最大权匹配）。

求解：

KM 算法可以在 $O(n^3)$ 时间求解二分图最大权匹配。

构造：