1. One-Liner
Run DFS on G to record finishing order, then DFS on Gᵀ in reverse finishing order — each tree in the second pass is an SCC.
2. The Problem It Solves
Same as Tarjan: strongly connected components — conceptually simpler two-pass method.
3. The Core Idea
The sink SCC (no edges to other SCCs) appears last in topological order of the condensation graph. Processing Gᵀ reverses reachability so you peel SCCs from sinks.
4. How It Works (Step-by-Step)
| Step | Action |
|---|---|
| 1 | DFS G, push vertex to order on exit |
| 2 | Build transpose Gᵀ (reverse all edges) |
| 3 | DFS Gᵀ in order reverse(postorder) |
| 4 | Each DFS tree = one SCC |
5. Dry Run Example
2-cycle 0↔1 and node 2→0: first pass order might end …2; second pass on Gᵀ discovers SCCs correctly.
6. Key Properties
| Property | Value |
|---|---|
| Clarity | Easier to prove than Tarjan |
| Memory | Must store Gᵀ |
7. Where It Is Used
| Domain | Use |
|---|---|
| Teaching / interviews | Standard SCC presentation |
| Same applications | As Tarjan |
8. Interview Tips
State why transpose; compare two passes vs Tarjan one pass.
9. Comparison with Other Algorithms
| Kosaraju | Tarjan | |
|---|---|---|
| Passes | 2 DFS | 1 DFS |
| Extra graph | Transpose | No |
10. Complexity
| -- | -- |
|---|---|
| Time | O(V + E) |
| Space | O(V + E) for transpose |
Implementation Example (PYTHON)
def kosaraju(n, adj):
vis = [False]*n
order = []
def dfs1(u):
vis[u]=True
for v in adj[u]:
if not vis[v]: dfs1(v)
order.append(u)
for i in range(n):
if not vis[i]: dfs1(i)
radj = [[] for _ in range(n)]
for u in range(n):
for v in adj[u]: radj[v].append(u)
vis = [False]*n; sccs = []
def dfs2(u, comp):
vis[u]=True; comp.append(u)
for v in radj[u]:
if not vis[v]: dfs2(v, comp)
for u in reversed(order):
if not vis[u]:
c=[]; dfs2(u,c); sccs.append(c)
return sccs