785. Is Graph Bipartite

Problem

Is Graph Bipartite?

Approach

We will try to label every node with color 0 or color 1. And during the process of labeling, if there is some node’s color is conflicted with the new color to be assigned, it shows that the result is fail. Or it success.

Code

class Solution {
    private boolean makeColor(int[][] graph, int id, int curColor, int[] color){
        if(color[id] != -1){
            return color[id] == curColor;
        }
        color[id] = curColor;
        for(int i = 0; i < graph[id].length; i ++){
            int j = graph[id][i];
            if(color[j] == -1){
                if(!makeColor(graph, j, (curColor + 1) % 2, color)){
                    return false;
                }
            } else {
                if(!makeColor(graph, j, (curColor + 1) % 2, color)){
                    return false;
                }
            }
        }
        return true;
    }
    public boolean isBipartite(int[][] graph) {
        int N = graph.length;
        int[] color = new int[N];
        for(int i = 0; i < N; i ++){
            color[i] = -1;
        }
        for(int i = 0; i < N; i ++){
            if(color[i] != -1){
                continue;
            }
            if(!makeColor(graph, i, 0, color)){
                return false;
            }
        }
        return true;
    }
}