Kosaraju's Algorithm - Steps

Here is how Kosaraju's algorithm works step by step:

$1.$ Run DFS on the original graph. When a node finishes (all descendants visited), push it to a stack.

$2.$ Build the transpose graph by reversing all edges. If $u \to v$ exists, create $v \to u$ instead.

$3.$ Pop nodes from the stack one by one. For each unvisited node, run DFS on the transpose graph.

$4.$ Each DFS tree from step $3$ is exactly one SCC.

Time complexity: $O(V + E)$ for both DFS passes combined. Space: $O(V)$ for the stack and visited arrays.