Bipartite Check
Two-colour the graph with BFS. An edge between two vertices of the same colour means an odd cycle.
DFS Checks: Two-colouring an even cycle
From 0 (colour 0), 1 is uncoloured: give it 1 and queue it.
Cost
- Best
- O(V + E)
- Average
- O(V + E)
- Worst
- O(V + E)
- Space
- O(V)
Before this
Leads to
Topics that need this one first.
Taught by the same lesson
DFS Checks covers these too, in the same run.