Leetcode 785: judgment bipartite graph

link

Ideas ：

The algorithm for determining bipartite graph is very simple , Is to use code to solve 「 Two color problem 」.
To put it bluntly, it is to traverse the graph , Dyeing while traversing , See if you can dye all nodes with two colors , And the colors of adjacent nodes are different .

class Solution {
    
    boolean a=true;
    boolean[] marked;
    boolean[] color;
    public boolean isBipartite(int[][] graph) {
    
        int n=graph.length;
        marked=new boolean[n];
        color=new boolean[n]; //  Automatically initialize to full false;
        // Traverse every vertex 
        for(int i=0;i<n;i++){
    
            dfs(graph,i);
        }
        return a;
    }

    void dfs(int[][] graph,int s){
    
        // Termination conditions ： If it is not a two fraction, there is no need to recurse 
        if(!a){
    
            return;
        }
        marked[s]=true; 
        // Traverse adjacency table 
        for(int k:graph[s]){
    
            if(!marked[k]){
     // Node not accessed 
                // Color  ！
                color[k]=!color[s];  // s  and k adjacent !  So different colors ！
                dfs(graph,k);
            }// Node has been accessed 
            if(color[k]==color[s]){
     //  The adjacent s and v The same color is not a bipartite graph 
                a=false;
            }
        }
    }
}