Kosaraju's Algorithm

Finds SCCs with two DFS passes: one on the graph (finish order), one on the reversed graph.

Advanced

Simpler to understand than Tarjan's; also $O(V+E)$ .

Spotted a mistake or want to add detail? Suggest an improvement — Content Contributors' edits are reviewed by editors before they go live.

Discussion (0)