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

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

下文记顶点数为 $n=|V|$，边数为 $m=|E|$。

判定

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

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

dfs 朴素染色即可，若出现相邻节点颜色相同则图不是二分图。每个点只会被染色一次，每条边只会被邻接表扫描常数次，所以时间复杂度为 $O(n+m)$。

点击展开代码

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 生成树；删去所有非树边后，每个连通块是一棵树，整个图剩下的是生成森林，而不一定是一棵树。

对于一条非树边 $(u,v)$，它与生成树上 $u$ 到 $v$ 的路径组成一个基环。树上路径长度的奇偶性等于 $de{p}_u+de{p}_v$ 的奇偶性，因此当 $de{p}_u,de{p}_v$ 同奇偶时，这条非树边会形成奇环。

反过来，若所有边的两个端点深度奇偶性都不同，那么直接按深度奇偶二染色即可。因此“不存在奇环”和“可以二染色”是等价的。

建立生成森林并扫描所有边，时间复杂度为 $O(n+m)$。

点击展开代码

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

扩展域并查集判二分图

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

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

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

初始化 $2n$ 个元素需要 $O(n)$，处理 $m$ 条边的并查集操作需要 $O(m\alpha (n))$，总时间复杂度为 $O(n+m\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 的。Kőnig 定理说明，在二分图上，最小点覆盖的大小等于最大匹配的大小，即 $|C_{min}|=|M_{max}|$。

构造：

先求出一组最大匹配 $M$，再从左部点集 $L$ 中所有未匹配点出发搜索交错路：从 $L$ 到 $R$ 只经过非匹配边，从 $R$ 到 $L$ 只经过匹配边。设搜索到的左右部点集分别为 $Z_L,Z_R$，则

$$C_{min}=(L\setminus Z_L)\cup Z_R.$$

不能从每条最大匹配边中任取一个端点；任意选择虽然恰好选出 $|M|$ 个点，却不保证覆盖所有非匹配边。

3.二分图最大独立集

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

求解：

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

构造：

取最小点覆盖补集。

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

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

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

求解：

DAG 的最小不相交路径覆盖 $=$ 顶点数量 $-$ 相应二分图 $G^{\prime }=(V^{\text{out}},V^{\text{in}},E^{\prime })$ 的最大匹配。具体地，对原图的每条边 $u\to v$，在 $G^{\prime }$ 中连接 $u^{\text{out}}$ 与 $v^{\text{in}}$。

构造：

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

这里选择最少数量的路径覆盖所有点，但允许一个点出现在多条路径中。它与上一节“不重复经过顶点”的路径覆盖不是同一个问题。

求解：

记原图为 $G$，求出传递闭包 $G^{+}$：若 $i$ 在 $G$ 中可以到达 $j$，就在 $G^{+}$ 中加入边 $i\to j$。在 $G^{+}$ 中，一条路径的相邻顶点只要求在原图中存在可达关系，因而可能跳过若干中间点。

对 $G^{+}$ 求不相交路径覆盖。若其拆点二分图的最大匹配大小为 $c$，则重复点路径覆盖的最小路径数为 $n-c$。把 $G^{+}$ 中的每条可达边展开成 $G$ 中的实际路径后，跳过的中间点可能出现在多条路径中，这正是“允许重复点”的来源。

如果题目允许直接把“可达”视为一步，可以输出 $G^{+}$ 中的路径；如果要求输出只由原图边组成的路径，则必须把每条可达边展开。若顶点不允许重复，则不能使用传递闭包替代原图，应使用上一节基于原边的构造。

使用 bitset 按逆拓扑序计算可达集合时，每条边可能触发一次长度为 $n$ 的按位或，时间复杂度为

$$O(n+m+\frac{n^2+mn}{w}),$$

其中 $w$ 是机器字位数；稠密图上最坏为 $O(n^3/w)$，空间复杂度为 $O(n^2/w)$ 个机器字。显式建立传递闭包还可能产生 $O(n^2)$ 条边，之后仍需另计最大匹配的时间。

构造：

先根据最大匹配把 $G^{+}$ 中的顶点连接成若干条链，再按需要将每条可达边替换为原图中的一条实际路径。

6. 二分图最大权匹配

二分图的最大权匹配是指二分图中边权和最大的匹配。若允许顶点不匹配，则空匹配也是合法方案，答案至少为 $0$，负权边没有必要被选择。相应地，把所有实边权设为 $1$ 时，最大权匹配就是最大匹配。

求解：

经典 KM 算法直接求解的是完全、等部二分图上的最大权完美匹配。设补全后两侧大小为 $N$，时间复杂度为 $O(N^3)$。用于其他目标时需要先明确建模：

• 若要求原图的完美匹配，缺失边不能当成普通的 $0$ 权边；应赋成不可选的负无穷，并在计算后验证答案没有使用缺失边。真实负权边可能被完美匹配强制选择。
• 若求允许不选边的任意大小最大权匹配，可以令 $N=max(|L|,|R|)$，用虚点补齐较小的一侧，并用权值为 $0$ 的人工边补成完全图。真实负权边也可按 $0$ 权人工选择处理；KM 得到完美匹配后，只保留其中被选中的真实正权边，其余人工边表示对应顶点未匹配。
• 若要求“先最大化匹配边数，再最大化权值”，则不能直接使用上一种 $0$ 权补边方式，需要先求最大匹配数，或给每条真实边增加足够大的统一权值以固定第一目标。

构造：

根据 KM 得到的匹配数组恢复配对；使用虚点或人工边建模时，需要删去这些不对应原图实边的配对。