Code link: https://leetcode.com/problems/is-graph-bipartite/

Constraint:

    graph.length == n
    1 <= n <= 100
    0 <= graph[u].length < n
    0 <= graph[u][i] <= n - 1
    graph[u] does not contain u.
    All the values of graph[u] are unique.
    If graph[u] contains v, then graph[v] contains u.

Idea

The idea is to use 2 different colors to mark each node. If there's an edge between u and v, then the color of u and v must be different. Otherwise there's a color conflict and it couldn't be a Bipartite graph. We could use BFS/DFS to traverse the graph. Initially set the node being visited as blue. Then when visiting its neighbors, set them as different color (red). If any of the neighbor already has a color set that is conflicting with current node, the graph is not a Bipartie.

Code

• BFS solution:

// A node could have 3 stages: 0 (unvisited), 1(red), -1 (blue). All nodes do not have any color at the begining. 
class Solution {
    public boolean isBipartite(int[][] graph) {
        int[] color = new int[graph.length];
        for (int u = 0; u < graph.length; u++) {
            if (color[u] != 0) {
                continue;
            }
            
            color[u] = 1;
            Queue<Integer> queue = new LinkedList<>();
            queue.offer(u);
            while (!queue.isEmpty()) {
                int cur = queue.poll();
                for (int neighbor : graph[cur]) {
                    if (color[cur] == color[neighbor]) {
                        return false;
                    } else if (color[neighbor] == 0) {
                        color[neighbor] = -color[cur];
                        queue.offer(neighbor);
                    }
                }
            }
        }
        
        return true;
    }
}

• Time: O(V + E), where V is the number of nodes in the graph and E is the number of edges in the graph.

• Space: O(V). The size of array to keep track of colors is V. The queue is to store the adjacent nodes for a given node, which could be V - 1.

• DFS solution:

class Solution {
   public boolean isBipartite(int[][] graph) {
       int[] nodeColor = new int[graph.length];
       for (int i = 0; i < graph.length; i++) {
           if (nodeColor[i] == 0 && !isValid(graph, nodeColor, i, 1)) {
               return false;
           }
       }
       
       return true;
   }
   
   private boolean isValid(int[][] graph, int[] nodeColor, int node, int colorToMark) {
       if (nodeColor[node] != 0) {
           return nodeColor[node] == colorToMark;
       }
       
       nodeColor[node] = colorToMark;
       for (int neighbor : graph[node]) {
           if (!isValid(graph, nodeColor, neighbor, -colorToMark)) {
               return false;
           }
       }
       
       return true;
   }
}

• Time and space complexity should be the same as BFS.

• Union find solution: