Is Graph Bipartite?
Problem
0..n-1 is given as an adjacency list
graph, where graph[u] holds the neighbours of u. Decide
whether the nodes can be split into two groups so that every edge connects a node of one
group to a node of the other. The graph may be disconnected.[[1,2,3],[0,2],[0,1,3],[0,2]]Outputfalse[[1,3],[0,2],[1,3],[0,2]]Outputtrue1 ≤ n ≤ 100 · no self-loops or parallel edges · if v ∈ graph[u] then u ∈ graph[v]
Try it yourself
class Solution {
public boolean isBipartite(int[][] graph) {
}
}
Instinct Connected regions, all paths, reachability, cloning or 2-colouring a graph or grid: dive from a node, mark it, recurse into unvisited neighbours.
Memory hack Mark before you march: go deep, paint as you go, and back up only when every door is already painted.
Open the Graph DFS guide →Approaches
Brute ForceBacktracking over All 2-Colourings
O(2n·(V+E))Space O(n)Place nodes one by one on side 1 or 2, skipping a side if an already-placed neighbour sits there; backtrack on a dead end. It ignores that colours are forced, so a late conflict re-tries choices for unrelated components — exponential.
public boolean isBipartite(int[][] graph) { return place(graph, new int[graph.length], 0); // side: 0 = unset, 1 or 2 } private boolean place(int[][] g, int[] side, int u) { if (u == g.length) return true; // every node placed, no clash for (int s = 1; s <= 2; s++) { boolean clash = false; for (int v : g[u]) if (side[v] == s) clash = true; if (clash) continue; side[u] = s; if (place(g, side, u + 1)) return true; } side[u] = 0; return false; }
Literal search of every split; hopeless beyond ~25 nodes.
BetterUnion-Find on “Same Side”
O((V+E)·log V)Space O(V)All neighbours of u must share one side (the one opposite
u), so union them together. If u ever lands in the same
set as one of its neighbours, an edge would stay inside one group → not
bipartite.
int[] parent; public boolean isBipartite(int[][] graph) { parent = new int[graph.length]; for (int i = 0; i < parent.length; i++) parent[i] = i; for (int u = 0; u < graph.length; u++) for (int v : graph[u]) { if (find(u) == find(v)) return false; // u and neighbour on same side parent[find(v)] = find(graph[u][0]); // all neighbours of u: one side } return true; } int find(int x) { return parent[x] == x ? x : (parent[x] = find(parent[x])); }
No recursion over the graph and works edge-by-edge, but path compression alone costs a log factor.
OptimalDFS Two-Colouring
O(V + E)Space O(V)For each uncoloured node (one per component) colour it 1 and DFS:
give every uncoloured neighbour the opposite colour -c. A neighbour that
already has colour c closes an odd cycle → return false.
public boolean isBipartite(int[][] graph) { int[] color = new int[graph.length]; // 0 = uncoloured, 1 / -1 = sides for (int i = 0; i < graph.length; i++) if (color[i] == 0 && !dfs(graph, color, i, 1)) return false; return true; } private boolean dfs(int[][] g, int[] color, int u, int c) { color[u] = c; for (int v : g[u]) { if (color[v] == c) return false; // edge inside one side if (color[v] == 0 && !dfs(g, color, v, -c)) return false; } return true; }
Each node and edge is touched once — linear and short.
At a glance
| Level | Approach | Time | Space |
|---|---|---|---|
| Brute Force | Backtracking over All 2-Colourings | O(2n·(V+E)) | O(n) |
| Better | Union-Find on “Same Side” | O((V+E)·log V) | O(V) |
| Optimal | DFS Two-Colouring | O(V + E) | O(V) |
- Starting only from node 0 — misses odd cycles in other components.
- Using
0both as “uncoloured” and as a colour. - Only checking uncoloured neighbours — the same-colour clash is the whole test.
- State the equivalence: bipartite ⇔ 2-colourable ⇔ no odd cycle.
- Point out colours are forced after the first pick — why no backtracking is needed.
- Mention Union-Find if edges arrive online.