785. Is Graph Bipartite?

It is a graph coloring problem. The basic idea is using group[i] to denote the group where ith node belongs to:

1. Initialize the group of each node to -1
2. dfs the graph to set the group of node whose group is -1.
3. If conflict occurs, return false.

Note that any two nodes on an edge must belong to different group.

public boolean isBipartite(int[][] graph) { 
    int group[] = new int[graph.length];
    Arrays.fill(group, -1);
    for(int i = 0; i < graph.length; i++) {
        if( group[i] == -1 && !help(i, graph, group, 0) )
            return false;
    }
    return true;
}

public boolean help(int index, int[][] graph, int group[], int color) {
    if( group[index] == color )
        return true;
    group[index] = color;
    for(int i = 0; i < graph[index].length; i++) {
        if( group[graph[index][i]] == color || !help(graph[index][i], graph, group, 1 - color) )
            return false;
    }
    return true;
}