785. Is Graph Bipartite?

Link

Solution

int[][] graph的描述讓人難懂。

graph[i]裡面擺的是跟 node-i 相鄰所有點。

ex. graph[0] = {1, 2} -> 表示node 0跟 node 1, node 2相接。

這題想到用dfs去對每個node塗色，若想塗色的時候發現該點已經被塗了，而且顏色跟我們預計要填的不一樣。那就是沒辦法成為二分圖。

 public boolean isBipartite(int[][] graph) {
        int n = graph.length;
        int[] color = new int[n];
        for(int i = 0; i < n; i++){
            if(color[i] == 0){                
                if(!dfs(graph, color, 1, i)) return false;
                
            }
        }
        return true;
    }
    
    public boolean dfs(int[][] graph, int[] color, int newColor, int i){
        
        if(color[i] != 0){
            if(color[i] != newColor) return false;
            if(color[i] == newColor) return true;
        }
        
        color[i] = newColor;
        
        for(int adj : graph[i]){
            if(!dfs(graph, color, -newColor, adj)) return false;
        }
        return true;
        
    }