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.

publicbooleanisBipartite(int[][] graph) { intn= graph.length; int[] colorArr = newint[n]; boolean[] marked = newboolean[n]; // dfs (graph may be disconnected, dfs on each unvisited node) for (inti=0; i < n; ++i) { if (!marked[i]) { if (!dfs(i, 0, graph, colorArr, marked)) returnfalse; } } returntrue; }

// color would be 0 or 1 privatebooleandfs(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]) returnfalse; } else { if (!dfs(w, color ^ 1, graph, colorArr, marked)) returnfalse; } } returntrue; }