力扣 886. 可能的二分法

题目来源：https://leetcode.cn/problems/possible-bipartition/

大致题意：
给一个整数 n，表示当前有 n 个人，他们的编号是 1 ~ n。再给一个二维数组，其中每个一维数组有两个元素，表示编号为第一个元素的人不喜欢编号为第二个元素的人

如果两个人不喜欢，那么就不能放在一个分组里，求 n 个人能否放在两个分组里

思路

每一个不喜欢的关系都可以看作一条边，那么所有关系和所有的人就组成了一张图

既然每条边都是不喜欢，那么边相连的两个顶点就需要在不同分组

于是可以使用一个数组表示每个节点对应的分组，然后对图进行遍历，遍历过程中需要判断当前相连节点之间的分组情况：

1. 节点 A 分组为 1，节点 B 没有分组。此时直接将节点 B 加入分组 B
2. 节点 A 分组为 1，节点 B 分组为 2，此时两个节点分组不同，无需处理
3. 节点 A 分组为 1，节点 B 分组为 1，两个节点分组相同，出现分组冲突

遍历时，若对应节点未分组，则以其为起点进行遍历，遍历过程中根据节点之间的关系进行判断和染色

解题步骤为：

1. 使用一个数组表示每个节点对应的分组，初始时都未分组
2. 根据给定关系建图
3. 遍历所有节点，若对应节点还未分组，则默认将其加入分组 1，并以其为起点进行遍历，遍历过程中根据节点之间的关系进行判断和染色。如果出现分组冲突直接返回false，表示不能分组
4. 如果未出现冲突，表示可以分组，返回 true

代码：

public boolean possibleBipartition(int n, int[][] dislikes) {
            int[] color = new int[n + 1];   // 存节点对应的分组
            List<Integer>[] edges = new List[n + 1];    // 存图
            for (int i = 0; i <= n; i++) {
                edges[i] = new ArrayList<>();
            }
            // 建图
            for (int[] relation : dislikes) {
                edges[relation[0]].add(relation[1]);
                edges[relation[1]].add(relation[0]);
            }
            // 遍历所有节点
            for (int i = 1; i <= n; i++) {
                // 若对应节点未分组
                if (color[i] == 0) {
                    // 以其为起点进行 BFS 遍历
                    Queue<Integer> queue = new ArrayDeque<>();
                    queue.add(i);
                    // 标记当前节点应该在的分组
                    boolean flag = false;
                    while (!queue.isEmpty()) {
                        // 根据标志位表示当前分组值
                        int temp = flag ? 1 : -1;
                        int size = queue.size();
                        // 取出当前步骤所有节点，并判断是否有分组冲突
                        for (int j = 0; j < size; j++) {
                            int cur = queue.poll();
                            // 当前节点分组
                            color[cur] = temp;
                            // 判断当前节点相连节点
                            for (int next : edges[cur]) {
                                // 如果未分组，加入队列
                                if (color[next] == 0) {
                                    queue.add(next);
                                } else {    // 如果已分组，判断是否冲突
                                    if (color[next] == temp) {
                                        return false;
                                    }
                                }
                            }
                        }
                        // 更新标志位
                        flag = !flag;
                    }
                }
            }
            return true;
        }
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