Possible Bipartition

题目
Given a set of N people (numbered 1, 2, ..., N), we would like to split everyone into two groups of any size.

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

Formally, if dislikes[i] = [a, b], it means it is not allowed to put the people numbered a and b into the same group.

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

答案

class Solution {
    public boolean possibleBipartition(int N, int[][] dislikes) {

        // Build a graph based on dislikes
        Map<Integer, Set<Integer>> g = new HashMap<>();
        int[] colors = new int[N + 1];
        Arrays.fill(colors, -1);
        for(int i = 0; i < dislikes.length; i++) {
            int a = dislikes[i][0];
            int b = dislikes[i][1];

            Set<Integer> neibr = g.get(a);
            if(neibr == null) {
                neibr = new HashSet<Integer>();
                g.put(a, neibr);
            }
            neibr.add(b);

            neibr = g.get(b);
            if(neibr == null) {
                neibr = new HashSet<Integer>();
                g.put(b, neibr);
            }
            neibr.add(a);
        }

        // Now, check if it's possible to paint the graph with 2 color

        for(int i = 1; i <= N; i++) {
            if(colors[i] == -1 && !paint(i, g, colors, 0))
                return false;
        }

        return true;
    }

    public boolean paint(int curr, Map<Integer, Set<Integer>> g, int[] colors, int color) {
        // If the node has been color before, check if the old color matches the new color
        if(colors[curr] != -1) {
            return colors[curr] == color;
        }
        colors[curr] = color;

        Set<Integer> neibr = g.get(curr);
        if(neibr == null) return true;
        for(int node : neibr) {
            if(!paint(node, g, colors, 1 - color))
                return false;
        }
        return true;
    }
}