785. Is Graph Bipartite?

undirected graph: all the connected nodes can be reached by visiting any node

directed graph: start from one node, may not traverse all connected nodes

class Solution {
    //0: unvisited, 1 set A, -1 set B
    int[] partition;
    boolean isBipartite;
    public boolean isBipartite(int[][] graph) {
        partition = new int[graph.length];
        isBipartite = true;
        for(int i = 0; i<graph.length; i++){
            // partition[i]==0 means unvisited;
            if(partition[i]==0){
                partition[i]=1;
                traverse(graph, i);
            }
        }
        return isBipartite;
    }
    
    private void traverse(int[][] graph, int index){
        if(!isBipartite) return;
        
        for(int next : graph[index]){
            if(partition[next]==0){
                partition[next] = -1*partition[index];
                traverse(graph, next);
            }else{
                if(partition[next]==partition[index]){
                    isBipartite = false;
                }
            }
        }
    }
}