1. One-Liner
A graph is bipartite iff it is 2-colorable: BFS/DFS assigns colors 0/1 so every edge connects opposite colors.
2. The Problem It Solves
Model two-sided relationships (workers/tasks, chessboard moves), detect odd-length cycles (non-bipartite), solve maximum bipartite matching setup.
3. The Core Idea
Bipartite ⇔ no odd cycle. Coloring propagates: neighbor must be opposite color; conflict ⇒ not bipartite.
4. How It Works (Step-by-Step)
| Step | Action |
|---|---|
| 1 | color = −1 unvisited |
| 2 | For each component: BFS from unvisited with color 0 |
| 3 | For edge u–v: if color[v]==color[u] → fail |
| 4 | Else assign opposite |
5. Dry Run Example
Even cycle C4: 2-colorable. Triangle C3: not bipartite — DFS finds neighbor same color.
6. Key Properties
| Property | Value |
|---|---|
| Trees | Always bipartite |
| Odd cycle | Obstruction |
7. Where It Is Used
| Domain | Use |
|---|---|
| Matching | Hopcroft–Karp preprocessing |
| LeetCode | Classic medium problem |
8. Interview Tips
Handle disconnected components. Directed graphs: use underlying undirected for 2-color.
9. Comparison with Other Algorithms
| Bipartite check | Graph coloring (general) | |
|---|---|---|
| Colors | 2 | NP-hard for ≥3 |
10. Complexity
| -- | -- |
|---|---|
| Time | O(V + E) |
| Space | O(V) |
Implementation Example (PYTHON)
from collections import deque
def is_bipartite(n, adj):
color = [-1] * n
for s in range(n):
if color[s] != -1: continue
color[s] = 0
q = deque([s])
while q:
u = q.popleft()
for v in adj[u]:
if color[v] == -1:
color[v] = color[u] ^ 1
q.append(v)
elif color[v] == color[u]:
return False
return True