The problem
Given an undirected graph as an adjacency list, decide whether its nodes can be split into two sets such that every edge connects a node from one set to the other.
Stuck? Reveal hints one at a time
How to approach it
- 1Keep a color array initialized to 0 (uncolored); colors are 1 and −1.
- 2For each uncolored node (graphs may be disconnected), BFS from it with color 1.
- 3When visiting a neighbor: if uncolored, give it the opposite color and enqueue; if it has the SAME color, return false.
- 4If every component colors cleanly, return true.
Key insight
Bipartite ⇔ no odd cycle. The coloring BFS is simply an odd-cycle detector: a same-color edge closes a cycle of odd length.
The solution
Watch out for
- Forgetting disconnected components — you must launch the coloring from every uncolored node.
- Self-loops make a graph instantly non-bipartite; the same-color check catches them naturally.