Possible Bipartition

https://leetcode.com/problems/possible-bipartition/description/

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.

1. 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

Thoughts

两两不合的关系自然形成了边，因此可以看成一个图。虽然题目描述像是一个有向图，其实a讨厌b和b讨厌a的效果是一样的，因此是无向图。大图里有一个或者多个联通子图，如过联通子图内部没有冲突，那么无论从哪个点开始染色，都能把它邻接结点染成相反的色，依次类推。有冲突时则要染的色和已被染的色冲突。

Code

class Solution {
    public boolean possibleBipartition(int N, int[][] dislikes) {
        Map<Integer, Integer> color = new HashMap<>();
        List<Integer>[] graph = new ArrayList[N + 1];
        for (int i = 1; i <= N; i++) {
            graph[i] = new ArrayList<>();
        }
        for (int[] edge : dislikes) {
            graph[edge[0]].add(edge[1]);
            graph[edge[1]].add(edge[0]);
        }

        for (int i = 1; i <= N; i++) {
            if (!color.containsKey(i) && !dfs(i, 0, color, graph)) {
                return false;
            }
        }

        return true;
    }

    private boolean dfs(int i, int c, Map<Integer, Integer> color, List<Integer>[] graph) {
        if (color.containsKey(i)) {
            if (color.get(i) != c) {
                return false;
            }
            return true;
        }

        color.put(i, c);

        for (int nei : graph[i]) {
            if (!dfs(nei, c ^ 1, color, graph)) {
                return false;
            }
        }
        return true;
    }
}

Analysis

时间复杂度O(N + E), 每个节点每条边都会被遍历一次。