#785
Is Graph Bipartite?
Medium 2-colouring with BFS
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Decide whether an undirected graph's nodes can be split into two groups so that every edge connects nodes from different groups.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: can nodes be split into two teams with every edge between teams?
Why this works: colour with two colours using BFS; a neighbour with your own colour means it's impossible.
Example: square 0-1-2-3-0
0 red, 1 blue, 2 red, 3 blue → no conflict → true✦Hints open one at a time
Try to colour nodes with two colours so neighbours always differ.
The graph may be disconnected — start a BFS from every uncoloured node.
↗Approach
color[] = 0 (none), 1 or −1. BFS: colour the start 1; give each uncoloured neighbour the opposite colour; if a neighbour already has the same colour, it's not bipartite.
</>Solution (Java)
import java.util.*;
class Solution {
public boolean isBipartite(int[][] graph) {
int n = graph.length;
int[] color = new int[n];
for (int s = 0; s < n; s++) {
if (color[s] != 0) continue;
color[s] = 1;
Queue<Integer> q = new ArrayDeque<>();
q.offer(s);
while (!q.isEmpty()) {
int u = q.poll();
for (int v : graph[u]) {
if (color[v] == color[u]) return false; // same side: conflict
if (color[v] == 0) {
color[v] = -color[u];
q.offer(v);
}
}
}
}
return true;
}
}!Common mistake
Only starting from node 0 and missing other components.
Complexity
- Time: O(V + E).
- Space: O(V).
Topic: Graphs
🎬 Episodes 74–85: video coming soon