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)$