AlgoViz
HomeGraphs

Kosaraju's algorithm

Hard

Order by finish time, then search the reverse graph

Problem

Find strongly connected components of a directed graph using Kosaraju's algorithm.

In simple words

DFS to order nodes, reverse edges, then DFS again to peel off each strongly-connected group.

The idea

Run DFS pushing each vertex onto a stack as it finishes, then reverse every edge and run DFS again popping from that stack. Each traversal in the second pass sweeps up exactly one strongly connected component.

The trick

  • Two DFS passes plus one graph reversal.
  • Finish-time order is what makes the second pass isolate components.
  • Tarjan's algorithm does it in one pass if you prefer.

This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.

0
0

Step 1 of 2. Here's the example — directed graph Values: 0.

1/2
Optimal
timeO(V+E)spaceO(V)
11) DFS pushing nodes by finish time22) transpose graph33) DFS in reverse finish order; each tree is one SCC

Input

array
[0]

Output

answer
—

Check yourself

2 quick questions about this walkthrough. A wrong answer costs nothing.

Example

Input:
directed graph
Output:
list of SCCs

Practice this problem:GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.