Grokking #229

class Solution {

    /*
      Choose no color = -1
      RED color = 0; BLUE color = 1
      We can switch the colors easily by "^" operator
    */
    static final int NO_COLOR = -1;
    List<List<Integer>> graph;
    int[] colors;


    public boolean possibleBipartition(int n, int[][] dislikes) {
        // create graph
        graph = new ArrayList<>();
        colors = new int[n + 1];
        Arrays.fill(colors, NO_COLOR);

        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<Integer>());
        }

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

        // check bipartite graph
        for (int at = 0; at <= n; at++) {
            // if vertex has no color, start coloring with 0 color
            if (colors[at] == NO_COLOR && !canColor(at, 0)) {
                return false;
            }
        }

        return true;
    }

    boolean canColor(int at, int color) {
        colors[at] = color;
        for (int to : graph.get(at)) {
            // if neighbor vertex has same color with current vertex, return false
            if (colors[to] == color) {
                return false;
            }

            // color neighbor vertex with alternative color
            // 0 ^ 1 = 1
            // 1 ^ 1 = 0
            if (colors[to] == NO_COLOR && !canColor(to, color ^ 1)) {
                return false;
            }
        }
        return true;
    }
}