可能的二分法 图解题解

这道题到底在问什么

输入

n=4, dislikes=[[1,2],[1,3],[2,4]]

输出

true(组1 {1,4} / 组2 {2,3})

输入

n=3, dislikes=[[1,2],[2,3],[1,3]]

输出

false(三人两两讨厌,奇环)

最优解：一步一步想明白

1. 3记住「建图 → BFS 染两色、相邻强制异色、撞同色就 false」,下面逐帧套它。
2. 4先把讨厌关系画成图:1 讨厌 2、1 讨厌 3、2 讨厌 4,连成三条边。此刻所有人都灰着、还没分组。
3. 5建好邻接表,记下每个人讨厌哪些人:1 讨厌 2、3;2 讨厌 1、4;3 讨厌 1;4 讨厌 2。color 数组全 0,表示还没人分组。
4. 6从还没染色的 1 号开始,把它放进组1(第一种颜色),并放进队列。一个连通块从这里开始扩散。
5. 7从队首取出 1 号(组1),看它讨厌的人:2、3。这些人都必须和 1 不同组。
6. 8顺着 1→2 这条讨厌边看 2 号:它现在是「未分组」。还没分组,得给它定一组。
7. 92 号还没分组。1 讨厌 2,所以把 2 染成和 1 相反的 组2,并入队等待处理。
8. 10顺着 1→3 这条讨厌边看 3 号:它现在是「未分组」。还没分组,得给它定一组。
9. 113 号还没分组。1 讨厌 3,所以把 3 染成和 1 相反的 组2,并入队等待处理。
10. 12从队首取出 2 号(组2),看它讨厌的人:1、4。这些人都必须和 2 不同组。
11. 13顺着 2→1 这条讨厌边看 1 号:它现在是「组1」。已经分过组了,核对一下会不会和 2 撞同组。
12. 141 号已经在 组1,和 2(组2)正好不同组,这对讨厌关系没问题,继续。
13. 15顺着 2→4 这条讨厌边看 4 号:它现在是「未分组」。还没分组,得给它定一组。
14. 164 号还没分组。2 讨厌 4,所以把 4 染成和 2 相反的 组1,并入队等待处理。
15. 17从队首取出 3 号(组2),看它讨厌的人:1。这些人都必须和 3 不同组。
16. 18顺着 3→1 这条讨厌边看 1 号:它现在是「组1」。已经分过组了,核对一下会不会和 3 撞同组。
17. 191 号已经在 组1,和 3(组2)正好不同组,这对讨厌关系没问题,继续。
18. 20从队首取出 4 号(组1),看它讨厌的人:2。这些人都必须和 4 不同组。
19. 21顺着 4→2 这条讨厌边看 2 号:它现在是「组2」。已经分过组了,核对一下会不会和 4 撞同组。
20. 222 号已经在 组2,和 4(组1)正好不同组,这对讨厌关系没问题,继续。
21. 23队列空了,所有人都染过色、全程没碰到任何「讨厌却同组」的冲突。分组成功:组1 {1, 4}、组2 {2, 3},返回 true。回头看,就是建图后 BFS 二染色、相邻强制异色,撞同色才失败。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from typing import List
from collections import deque
class Solution:
    def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:
        g = [[] for _ in range(n + 1)]
        for a, b in dislikes:
            g[a].append(b); g[b].append(a)
        color = [0] * (n + 1)
        for i in range(1, n + 1):
            if color[i]:
                continue
            color[i] = 1
            q = deque([i])
            while q:
                u = q.popleft()
                for v in g[u]:
                    if color[v] == color[u]:
                        return False
                    if color[v] == 0:
                        color[v] = -color[u]
                        q.append(v)
        return True

#include <queue>
#include <vector>
using namespace std;
class Solution {
public:
    bool possibleBipartition(int n, vector<vector<int>>& dislikes) {
        vector<vector<int>> g(n + 1);
        for (auto &e : dislikes) { g[e[0]].push_back(e[1]); g[e[1]].push_back(e[0]); }
        vector<int> color(n + 1);
        for (int i = 1; i <= n; ++i) if (!color[i]) {
            queue<int> q; q.push(i); color[i] = 1;
            while (!q.empty()) {
                int u = q.front(); q.pop();
                for (int v : g[u]) {
                    if (color[v] == color[u]) return false;
                    if (!color[v]) { color[v] = -color[u]; q.push(v); }
                }
            }
        }
        return true;
    }
};

import java.util.*;
class Solution {
    public boolean possibleBipartition(int n, int[][] dislikes) {
        List<Integer>[] g = new ArrayList[n + 1];
        for (int i = 1; i <= n; i++) g[i] = new ArrayList<>();
        for (int[] e : dislikes) { g[e[0]].add(e[1]); g[e[1]].add(e[0]); }
        int[] color = new int[n + 1];
        Queue<Integer> q = new ArrayDeque<>();
        for (int i = 1; i <= n; i++) if (color[i] == 0) {
            color[i] = 1; q.offer(i);
            while (!q.isEmpty()) {
                int u = q.poll();
                for (int v : g[u]) {
                    if (color[v] == color[u]) return false;
                    if (color[v] == 0) { color[v] = -color[u]; q.offer(v); }
                }
            }
        }
        return true;
    }
}

复杂度

面试官可能追问