LeetCode 886. 可能的二分法
目录
题目描述
题意分析
题目给 $n$ 个编号从 1 到 $n$ 的人，以及若干「互相讨厌」的人对，问能不能把所有人分成两组，使得任何一对互相讨厌的人都不落在同一组，只需回答能或不能。
要注意题目没有要求两组人数相等，也没有要求两组都非空，甚至没有要求同组的人彼此友好——唯一的硬约束就是每一条讨厌关系的两端必须分属不同组。这意味着我们真正要判定的是一个纯粹的结构性质，而不是去构造某种最优分配。
约束里 $n$ 最大 2000，讨厌关系最多 $10^4$ 条，关系数远小于 $n^2$，说明这是一张稀疏的关系网，适合按关系列表逐条建索引，而不是开一张 $2000 \times 2000$ 的表。同时数据量级明确允许一次线性遍历。
边界上要留意三点：编号从 1 开始，容器要多留一格否则下标错位；讨厌关系列表可能为空，此时随便怎么分都行；最容易漏的是这张关系网未必连通，几个互不相干的小团体各自成块，必须把每一块都检查到。
解法：二分图判定
核心思路
把人看成节点、把每一对互相讨厌的人之间连一条无向边，问题就变成了「能否给所有节点涂上两种颜色，使得每条边的两个端点异色」。
暴力做法是枚举每个人属于哪一组，共 $2^n$ 种分法，逐一验证全部边。$n$ 到 2000 时这条路彻底不可行。
瓶颈在于暴力把 $n$ 个人的归属当成 $n$ 个自由变量分别枚举，而它们其实根本不自由。关键观察是：只要任意固定一个人的组别，与他有边相连的人的组别就被完全确定（必须在另一组），这些人的邻居又被进一步确定，如此沿着边一路传播下去，整个连通块里每个人的组别都被那一个初始选择唯一钉死。换句话说，一个连通块只有两种整体方案，且互为镜像——把两组对调而已，谁能成立谁不能成立完全一致。
于是自由度从 $2^n$ 塌缩到「每个连通块二选一」，而这两种选择又是等价的，所以我们只需在每个连通块里任选一个起点、随便给它一种颜色，然后把强制传播的结果全部推出来，看会不会撞车。
由此写下遍历过程的不变量：
color[v] = 0表示 $v$ 还没被任何传播触及；color[v]非 0 时，它就是「在本连通块起点被定为颜色 1 的前提下，$v$ 唯一可能的颜色」。传播时若遇到一个已着色的邻居与当前节点同色，说明这两个人被强制要求既同组又不同组，矛盾无法通过换起点颜色化解（因为换色只是整体取反，同色关系不变），可以立刻断定无解。传播用 BFS 还是 DFS 都行，本质都是沿边扩散；这里用队列实现，颜色取 1 与 -1，取反只需一个负号，比布尔值更省判断。最后，因为关系网可能有多个互不相连的块，外层必须把 1 到 $n$ 每个人都过一遍，遇到还没着色的就作为一个新块的起点重新发起传播。
解题步骤
- 建立长度为 $n + 1$ 的邻接表，把每条讨厌关系 $(a, b)$ 双向登记：
graph[a]加入b，graph[b]加入a。为什么长度是 $n + 1$：编号从 1 开始，多留一格可以让下标和编号直接对齐，省掉全篇的减一。为什么必须双向：讨厌是对称关系，只登记一个方向的话，从另一端出发时看不到这条约束，着色顺序一变结论就变。- 开一个长度 $n + 1$ 的
color数组，全部初始化为 0 代表未着色。为什么用 0 而不是布尔数组：需要区分「未着色」「颜色一」「颜色二」三种状态，布尔只能表达两种。- 外层从 1 到 $n$ 遍历，跳过已着色的人；遇到未着色的人，把他当作一个新连通块的起点，着成颜色 1 并入队。为什么要外层循环：关系网可能分裂成多个互不相连的块，只从某一个点出发会漏掉其余块里的矛盾。为什么可以随便给起点一种颜色：整块方案只有互为镜像的两种，起点取哪一种不影响是否存在矛盾。
- 队列非空时取出一个人，遍历他的所有邻居。邻居未着色就染成当前节点颜色的相反色并入队；邻居已着色且与当前节点同色，立刻返回 false。为什么同色就能直接否定：这条边要求两端异色，而两端的颜色都是由同一个起点强制推出的、没有其他可能，矛盾无法回避。
- 全部人都处理完还没撞车，返回 true。
以
n = 4, dislikes = [[1,2],[1,3],[2,4]]走一遍：建图后graph[1] = [2,3]、graph[2] = [1,4]、graph[3] = [1]、graph[4] = [2]，color初始全 0。外层 $i = 1$，未着色，令
color[1] = 1并入队，队列为[1]。出队 1，遍历邻居：2 未着色，染成 $-1$ 入队；3 未着色，也染成 $-1$ 入队。此时
color = [_, 1, -1, -1, 0]，队列为[2, 3]。出队 2，遍历邻居：1 已着色为 1，与
color[2] = -1不同，检查通过；4 未着色，染成-color[2] = 1入队。此时color = [_, 1, -1, -1, 1]，队列为[3, 4]。出队 3，邻居只有 1，颜色 1 与
color[3] = -1不同，通过。出队 4，邻居只有 2，颜色 $-1$ 与
color[4] = 1不同，通过。队列清空，第一个连通块检查完毕。外层继续到 $i = 2, 3, 4$，三人均已着色，直接跳过。遍历结束返回 true，对应的分组是 ${1, 4}$ 与 ${2, 3}$，三条讨厌关系的两端确实都被分开了。
再看矛盾是怎么暴露的：把输入换成
n = 3, dislikes = [[1,2],[1,3],[2,3]]。color[1] = 1入队；出队 1 时把 2 和 3 都染成 $-1$；出队 2 时先看邻居 1（颜色 1，通过），再看邻居 3——color[3] = -1与color[2] = -1相同，三个人两两讨厌却只有两组可用，当场返回 false。
代码实现
class Solution {
// 使用 BFS/DFS 进行二染色，若出现相邻节点同色则不可二分。
public boolean possibleBipartition(int n, int[][] dislikes) {
List<Integer>[] graph = new List[n + 1];
for (int i = 1; i <= n; i++) {
graph[i] = new ArrayList<>();
}
for (int[] d : dislikes) {
graph[d[0]].add(d[1]);
graph[d[1]].add(d[0]);
}
int[] color = new int[n + 1];
for (int i = 1; i <= n; i++) {
if (color[i] != 0) {
continue;
}
Deque<Integer> queue = new ArrayDeque<>();
queue.offer(i);
color[i] = 1;
while (!queue.isEmpty()) {
int cur = queue.poll();
for (int next : graph[cur]) {
if (color[next] == 0) {
color[next] = -color[cur];
queue.offer(next);
} else if (color[next] == color[cur]) {
return false;
}
}
}
}
return true;
}
}
func possibleBipartition(n int, dislikes [][]int) bool {
// 使用 BFS/DFS 进行二染色，若出现相邻节点同色则不可二分。
graph := make([][]int, n+1)
for _, d := range dislikes {
graph[d[0]] = append(graph[d[0]], d[1])
graph[d[1]] = append(graph[d[1]], d[0])
}
color := make([]int, n+1)
for i := 1; i <= n; i++ {
if color[i] != 0 {
continue
}
queue := make([]int, 0)
queue = append(queue, i)
color[i] = 1
for len(queue) > 0 {
cur := queue[0]
queue = queue[1:]
for _, next := range graph[cur] {
if color[next] == 0 {
color[next] = -color[cur]
queue = append(queue, next)
} else if color[next] == color[cur] {
return false
}
}
}
}
return true
}
复杂度分析
- 时间复杂度：$O(n + m)$，其中 $n$ 是人数、$m$ 是讨厌关系数。建图把每条关系登记两次是 $O(m)$；外层循环访问每个人一次，每个人只在未着色时入队一次、出队一次，出队时扫一遍他的邻接表，所有邻接表长度之和恰好是 $2m$。
- 空间复杂度：$O(n + m)$，邻接表要存下 $2m$ 个方向条目、
color数组占 $n + 1$ 格，队列最多同时容纳 $n$ 个人；这三项都随输入增长，不是常数级。
关键点总结
- 看到「分成两组且某些对不能同组」，要立刻把它翻译成图的二染色判定。识别出问题的图论外壳，比记住 BFS 模板重要得多。
- 把「自由度」算清楚是降复杂度的关键：固定一个起点的颜色后，整个连通块被唯一确定，$2^n$ 的搜索空间因此塌缩成每块二选一，而这两种选择互为镜像、等价，于是连枚举都省了。
- 用三态的整型
color而不是布尔visited，一个数组同时承担「是否访问过」和「属于哪组」两件事；取值选 1 与 -1 而非 0 与 1，取反只用一个负号。- 图不保证连通是这类题最高频的陷阱，外层遍历所有顶点是标配；同理，也不要假设每个人都出现在关系列表里。
- 面试视角：写完 BFS 后主动补一句「换成 DFS 递归染色完全等价，但递归深度最坏是 $O(n)$」，再补一句「也可以用扩展域并查集，把每个人拆成自己和敌人两个域来做」，能一次性展示对三种主流写法的掌握。
- 面试视角：常见追问是「如果要分成三组呢」。答案是问题立刻变成图的三染色，属于 NP 完全，不存在类似的线性算法——能指出这条分界线，说明你理解的是问题的本质而非模板。
易错点总结
- 错误写法：建图时只登记单向边，写成只往
graph[d[0]]里加d[1]。用例n = 2, dislikes = [[2,1]]→ 人 1 的邻接表为空，被单独染成颜色 1；人 2 未着色又被当作新块起点染成颜色 1，检查邻居 1 时发现同色，返回 false，正确答案是 true。- 错误写法：只从编号 1 出发做一次 BFS，不遍历其余节点。用例
n = 4, dislikes = [[2,3],[3,4],[2,4]]→ 人 1 孤立，一轮 BFS 后就结束，2、3、4 构成的三角形从未被检查，返回 true，正确答案是 false。- 错误写法：数组按 $n$ 而非 $n + 1$ 开辟，编号却直接当下标用。用例 任意含编号 $n$ 的关系（如
n = 2, dislikes = [[1,2]]）→ 访问graph[2]直接数组越界。- 错误写法：用布尔
visited数组代替三态颜色。用例n = 3, dislikes = [[1,2],[1,3],[2,3]]→ 只能判断是否访问过，无法比较组别，三角形的矛盾检测不出来，返回 true，正确答案是 false。- 错误写法：起点只入队却忘了同时着色。用例 任意含边的输入 → 起点
color仍是 0，邻居被染成-0也就是 0，等于没染色，这些人被反复判定为未访问并重复入队，队列不断膨胀。- 错误写法：发现相邻同色时只
continue跳过而不返回 false。用例n = 3, dislikes = [[1,2],[1,3],[2,3]]→ 矛盾被吞掉，最终返回 true，正确答案是 false。- 错误写法：把「互相讨厌」理解成可以合并的等价关系，直接用并查集把两人合并到同一集合。用例
n = 3, dislikes = [[1,2],[2,3]]→ 三人被并成一个集合并判定冲突，返回 false，正确答案是 true（分成 ${1,3}$ 与 ${2}$ 即可）；并查集的正确用法是合并「敌人的敌人」或使用扩展域。- 错误写法：把颜色取成 0 和 1，同时又用 0 表示未着色。用例 任意含边的输入 → 被染成 0 号色的人和未着色的人无法区分，会被再次入队重染，既可能死循环也可能漏判矛盾。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 785. 判断二分图 | 中等 | 直接给出邻接表，省去从关系对建图这一步 |
| LCR 106. 判断二分图 | 中等 | 与 785 输入一致，适合改用扩展域并查集再练一遍 |
| 990. 等式方程的可满足性 | 中等 | 约束分等号与不等号两类，须先合并再统一校验 |
| 207. 课程表 | 中等 | 有向图判环，靠拓扑排序而非染色传播 |