886 Possible Bipartition

886. Possible Bipartition

1. Question

Given a set ofN people (numbered1, 2, ..., N), we would like to split everyone into two groups ofanysize.

Each person may dislike some other people, and they should not go into the same group.

Formally, ifdislikes[i] = [a, b], it means it is not allowed to put the people numberedaandbinto the same group.

Returntrue if and only if it is possible to split everyone into two groups in this way.

Example 1:

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

Example 2:

Input: 
N = 3, dislikes = [[1,2],[1,3],[2,3]]
Output: false

Example 3:

Input: 
N = 5, dislikes = [[1,2],[2,3],[3,4],[4,5],[1,5]]
Output: false

Note:

1. 1 <= N <= 2000

2. 0 <= dislikes.length <= 10000

3. 1 <= dislikes[i][j] <= N

4. dislikes[i][0] < dislikes[i][1]

5. There does not existi != jfor whichdislikes[i] == dislikes[j].

2. Implementation

思路: 用BFS对图进行染色，如果相邻的点是不同颜色，则可以分成二分图

class Solution {
    public boolean possibleBipartition(int N, int[][] dislikes) {
        int[] colors = new int[N + 1];
        Arrays.fill(colors, -1);

        List<Set<Integer>> adjList = new ArrayList();

        for (int i = 0; i <= N; i++) {
            adjList.add(new HashSet());
        }

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

        Queue<Integer> queue = new LinkedList();


        for (int i = 1; i <= N; i++) {
            if (colors[i] == -1) {
                colors[i] = 1;
                queue.add(i);

                while (!queue.isEmpty()) {
                    int curNode = queue.remove();

                    for (int nextNode : adjList.get(curNode)) {
                        if (colors[nextNode] == -1) {
                            colors[nextNode] = 1 - colors[curNode];
                            queue.add(nextNode);
                        }
                        else if (colors[nextNode] == colors[curNode]) {
                            return false;
                        }
                    }
                }
            }
        }
        return true;
    }
}

3. Time & Space Complexity

时间复杂度O(n), 空间复杂度O(n)