AlgoScope

Kosaraju

Finish order from one DFS, reverse every edge, then DFS from the latest finisher to paint each component.

Connectivity and topological order, algorithm, advanced
Start pass 2 from 0.07162534435162u
Start pass 2 from 0.07162534435162u

Bridges and Components: Kosaraju on the same graph

Decision, step 17 of 27

Pass 2: the unassigned vertex with the latest finish time is 0, finish 7. Start a DFS there on the reversed graph. It opens component 0.

How bridges and components works

Cost

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

Taught by the same lesson

Bridges and Components covers these too, in the same run.