LeetCode 886. Possible Bipartition
2020-05-28 20:09:15 # leetcode # dfs # graph # bfs

Problem

LeetCode 886. Possible Bipartition

1. 题目简述

给出n个人，编号从(1…n)，我们可以将他们分成任意大小的两组，但是他们之间会有讨厌某些人的关系，那么他们就不用管被分到同一个组里。

用公式化的形式来讲，就是如果dislikes[i] = [a, b]，那么a和b就不会被分到同一个组里。我们需要判断能否做到合适的分组，满足所有dislike条件。

Input: N = 4, dislikes = [[1,2],[1,3],[2,4]]
Output: true
Explanation: group1 [1,4], group2 [2,3]

2. 算法思路

经典的二分图算法，和785是一样的，只不过本题需要先把整张dislike图给construct出来。染色，然后判断是否ok。

DFS

BFS

注意

首先将整张dislike图build出来，因为我们并不知道每个人究竟有多少个dislike的对象，所以可以用ArrayList的数组来存储。这里需要注意ArrayList数组的初始化问题！！！ArrayList数组应该这样初始化，注释中的做法不可用！！！

原因在于foreach不能用于元素赋值或初始化，而是将数组中元素copy一份给临时变量。

1
2
3
4
5
6
7
8
9
10

ArrayList<Integer>[] dislikeGraph = new ArrayList[N + 1];

// for (List<Integer> list : dislikeGraph) {
//     list = new ArrayList();
// }

for (int i = 0; i <= N; i++) {
    dislikeGraph[i] = new ArrayList();
}

3. 解法

DFS：

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

class Solution {
        // 注意List数组的创建！！！
        ArrayList<Integer>[] dislikeGraph = new ArrayList[N + 1];

        for (int i = 0; i <= N; i++) {
            dislikeGraph[i] = new ArrayList();
        }

        for (int[] dislike : dislikes) {
            dislikeGraph[dislike[0]].add(dislike[1]);
            dislikeGraph[dislike[1]].add(dislike[0]);
        }

        // DFS, -1是未访问，0是red，1是black
        int[] isVisited = new int[N + 1];
        Arrays.fill(isVisited, -1);

        for (int i = 1; i <= N; i++) {
            if (isVisited[i] != -1) {
                continue;
            }
            // 注意这里给上的颜色，如果已经遍历过，有颜色，则说明该节点没问题，跳过即可
            isVisited[i] = 0;
            if (!dfs(dislikeGraph, isVisited, i)) {
                return false;
            }
        }

        return true;
    }

    private boolean dfs(List<Integer>[] dislikeGraph, int[] isVisited, int index) {
        for (int i : dislikeGraph[index]) {
            if (isVisited[i] == -1) {
                isVisited[i] = isVisited[index] ^ 1;
                if (!dfs(dislikeGraph, isVisited, i)) {
                    return false;
                }
            } else if (isVisited[i] != (isVisited[index] ^ 1)) {
                return false;
            }
        }

        return true;
    }
}

BFS：
下次看到这里再留着练手吧

Prev
2020-05-28 20:09:15 # leetcode # dfs # graph # bfs
Next