Leetcode: Check to see if Graph is Bipartite

 

This question is asked at Facebook, TikTok and Ebay and is commonly discussed in Algorithms classes. 

There is an undirected graph with n nodes where each node is numbered and given a 2D adjacent array graph. There are no self-edges and parallel edges (duplicate values). The graph is also undirected (v in u and u in v) and the graph might not be connected which means there may only be 2 nodes connected. 

A graph is bipartite if the nodes can be partitioned into independent sets such that every edge connects a node in set A to a node in set B. 

Here's an example: 

Input: graph = [[1,2,3],[0,2],[0,1,3],[0,2]]

Output: false

Explanation: There is no way to partition the nodes into two independent sets such that every edge connects a node in one and a node in the other.

This is because 2 and 1 and 3 have to be in the same set, but different sets at the same time with 0. So we must assign "sets" or "colors" to each element of the bipartite graph. 

So we can color a node blue if it is part of the first set, otherwise, we'll color the node red. We'll keep a hashmap or array to look up the color of each node, and should consider the disconnected components of a graph by searching for each node. WE can use a stack for DFS and we'll color a node for each uncolored node, otherwise check if the color is corresponding, we can utilize a boolean for this. 

Here is the code, with detailed commentary:

class Solution {

    public boolean isBipartite(int[][] graph) {

        int n = graph.length;

        int[] color = new int[n];

        //initially there is no color 

        Arrays.fill(color, -1);

        //go over each node of the graph

        for (int start = 0; start < n; ++start) {

            if (color[start] == -1) {

                //initialize a stack

                Stack<Integer> stack = new Stack();

                stack.push(start);

                //fill in the first color. 

                color[start] = 0;

                while (!stack.empty()) {

                    //perform color checking. Don't need to mark here

                    Integer node = stack.pop();

                    //figure out the color

                    for (int nei: graph[node]) {

                        if (color[nei] == -1) {

                            stack.push(nei);

                            color[nei] = color[node] ^ 1;

                        } else if (color[nei] == color[node]) {

                            //color for adjacent nodes can't be the same. 

                            return false;

                        }

                    }

                }

            }

        }

        //all the conditions are passed. 

        return true;

    }

}