AlgoScope

Bipartite Check

Two-colour the graph with BFS. An edge between two vertices of the same colour means an odd cycle.

Graph traversal, algorithm, intermediate
1 coloured 1.00112345
1 coloured 1.00112345

DFS Checks: Two-colouring an even cycle

Decision, step 3 of 15

From 0 (colour 0), 1 is uncoloured: give it 1 and queue it.

How dfs checks works

Cost

Best
O(V + E)
Average
O(V + E)
Worst
O(V + E)
Space
O(V)

Leads to

Topics that need this one first.

Taught by the same lesson

DFS Checks covers these too, in the same run.