Reference: LeetCode
Difficulty:

Problem

Check if a graph is bipartite? The graph could be disconnected.

Note: There are no self edges or parallel edges.

Example: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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.

Analysis

DFS or BFS

Note: Graph may be disconnected, so we should do DFS on each unvisited node.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public boolean isBipartite(int[][] graph) {
  int n = graph.length;
  int[] colorArr = new int[n];
  boolean[] marked = new boolean[n];
  // dfs (graph may be disconnected, dfs on each unvisited node)
  for (int i = 0; i < n; ++i) {
    if (!marked[i]) {
      if (!dfs(i, 0, graph, colorArr, marked)) return false;
    }
  }
  return true;
}

// color would be 0 or 1
private boolean dfs(int v, int color, int[][] graph, int[] colorArr, boolean[] marked) {
  // visit
  marked[v] = true;
  colorArr[v] = color;
  // neighbors
  for (int w : graph[v]) {
    if (marked[w]) {
      // check if it is the same color
      if (colorArr[v] == colorArr[w]) return false;
    } else {
      if (!dfs(w, color ^ 1, graph, colorArr, marked)) return false;
    }
  }
  return true;
}

Time: $O(V + E)$
Space: $O(V)$