MockInterview:785. Is Graph Bipartite?

Medium

Given an undirected graph, return true if and only if it is bipartite.

Recall that a graph is bipartite if we can split it's set of nodes into two independent subsets A and B such that every edge in the graph has one node in A and another node in B.

The graph is given in the following form: graph[i] is a list of indexes j for which the edge between nodes i and j exists.  Each node is an integer between 0 and graph.length - 1.  There are no self edges or parallel edges: graph[i] does not contain i, and it doesn't contain any element twice.

Example 1:
Input: [[1,3], [0,2], [1,3], [0,2]]
Output: true
Explanation: 
The graph looks like this:
0----1
|    |
|    |
3----2
We can divide the vertices into two groups: {0, 2} and {1, 3}.

Example 2:
Input: [[1,2,3], [0,2], [0,1,3], [0,2]]
Output: false
Explanation: 
The graph looks like this:
0----1
| \  |
|  \ |
3----2
We cannot find a way to divide the set of nodes into two independent subsets.

Solution: use two color to color the graph.

1) assign red color to the source vertex.

2) color all neighbors with blue color.

3) color all neighbors' neighbors with red color.

4) while assign the color, find a neighbor which is colored the same color with current vertex.

initialize a color[] array for each node, here are three states for color[] array.

1: red;

-1: blue;

0: haven't been colored yet.

for each node

1) if it hasn't been colored, use a color( which is passed from caller) to color it. color the other color to its adjacent node. check each adjacent node has the correct color, if adjacent node return false, it return false directly.

2) if it has been colored, check whether the color is the same as the color which is going to color it(passed by its caller); if it's different, return false;

class Solution {
    public boolean isBipartite(int[][] graph) {
        int n = graph.length;
        int[] colorArr = new int[n];
        
        for(int i = 0; i < n; i++){
            if(colorArr[i] == 0){

  //This graph might be a disconnected graph. So check each unvisited node.
                if(!dfs(graph, colorArr, 1, i)){//
                    return false;
                }
            }
        }
        
        return true;
    }
    
    private boolean dfs(int[][] graph, int[] colorArr, int toColor, int index){
        if(colorArr[index] != 0){
            if(colorArr[index] != toColor){
                return false;
            }
        }else{
            int[] edges = graph[index];
            colorArr[index] = toColor;
            for(int next : edges){
                if(!dfs(graph, colorArr, -toColor, next))
                    return false;
            }
        }
        return true;
    }
}