我的算法书 - 二分图判定：黑白染色

一句话算法

黑白染色就是强制相邻点颜色不同；如果某条边两端颜色相同，图中一定存在奇环，不是二分图。

问题模型

给定一张无向图，判断能否把所有点分成两个集合 $L$ 和 $R$ ，使得每条边的两个端点分别属于不同集合。

这样的图叫二分图。

等价说法：

图可以被两种颜色染色；
任意一条边连接的两个点颜色不同；
图中不存在奇环。

核心直觉

从任意未染色点开始，把它染成黑色。它的所有邻点必须是白色；邻点的邻点又必须是黑色。

这个过程没有选择空间：

u 是黑色 -> 所有邻点必须是白色
v 是白色 -> 所有邻点必须是黑色

如果某次发现一条边连接了两个同色点，说明前面的强制染色产生冲突。这个冲突本质上来自一条奇数长度的环。

算法步骤

初始化所有点颜色为 0，表示未染色。
枚举每个点，若它未染色，就从它开始 BFS。
起点染成 1。
弹出队首点 u，枚举邻点 v：
- 若 v 未染色，令 color[v] = 3 - color[u]；
- 若 v 已染色且 color[v] == color[u]，说明不是二分图。
所有连通块都没有冲突，则整张图是二分图。

算法证明

核心不变量：BFS 过程中，每条已经检查过的边两端颜色都不同。

起点可以任意染色，不影响是否存在二分划分。
当访问边 u-v 时，如果 v 未染色，把它染成 u 的相反颜色，当前边合法。
如果 v 已染色且颜色不同，当前边合法。
如果 v 已染色且颜色相同，则所有染色都是由路径长度奇偶强制推出来的。出现同色边，意味着存在一条奇环，无法二分。
若算法结束没有冲突，把颜色为 1 的点放入一侧，颜色为 2 的点放入另一侧，每条边两端颜色不同，因此是合法二分。

所以算法正确。

复杂度分析

设点数为 $n$ ，边数为 $m$ 。

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

代码实现

cpp

        1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

        #include <bits/stdc++.h>
using namespace std;

struct BipartiteChecker {
    int n = 0;
    vector<vector<int>> graph;
    vector<int> color; // 0: uncolored, 1 and 2: two sides.

    BipartiteChecker(int n = 0) {
        init(n);
    }

    void init(int node_count) {
        n = node_count;
        graph.assign(n + 1, {});
        color.assign(n + 1, 0);
    }

    void add_edge(int u, int v) {
        graph[u].push_back(v);
        graph[v].push_back(u);
    }

    bool bfs_color(int start) {
        queue<int> q;
        color[start] = 1;
        q.push(start);

        while (!q.empty()) {
            int u = q.front();
            q.pop();

            for (int v : graph[u]) {
                if (color[v] == 0) {
                    color[v] = 3 - color[u];
                    q.push(v);
                } else if (color[v] == color[u]) {
                    return false;
                }
            }
        }

        return true;
    }

    bool is_bipartite() {
        for (int i = 1; i <= n; i++) {
            if (color[i] == 0 && !bfs_color(i)) {
                return false;
            }
        }
        return true;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    BipartiteChecker checker(n);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        checker.add_edge(u, v);
    }

    cout << (checker.is_bipartite() ? "Yes" : "No") << '\n';
    return 0;
}

测试用例

输入：

输出：

Yes

如果加入边 1 3，图中出现三角形 1-2-3-1，输出应为：

No

应用分类详解

黑白染色的本质是检查“相邻对象必须属于相反阵营”的约束是否自洽。

一、二分图判定

典型模式： 判断图能否分成左右两部分。

识别信号： 题面出现“相邻不能同组”“敌人关系”“两种类型”。

核心建模： 点是对象，冲突关系是边，颜色表示所属集合。

应用场景	经典题目	核心思路
二分图模板	luogu-P3386	先判二分，再做匹配
染色冲突	luogu-P1330	每个连通块二选一取较小颜色

二、奇环判定

典型模式： 判断无向图是否存在奇环。

识别信号： 出现“奇环”“不能黑白染色”“关系矛盾”。

核心建模： 二分图等价于没有奇环。染色冲突就是奇环证据。

三、种类并查集的替代视角

典型模式： 约束是“不同类”。

识别信号： 只有两种阵营，并且每条关系要求两端相反。

核心建模： 在线增量约束常用种类并查集；离线整图判断可用黑白染色。

经典例题

1. luogu-P1330

封锁阳光大学。每个连通块必须黑白染色，答案取两种颜色人数较小者。

2. luogu-P3386

二分图最大匹配模板。黑白染色可以作为判断二分图和划分左右部的前置步骤。

3. poj-2492

经典关系矛盾题。可以用黑白染色或种类并查集判断是否存在冲突。