GeeksforGeeks Hard

Strongly Connected Components (Kosaraju)

Split a directed graph into strongly connected components — maximal groups where every vertex reaches every other.

graphdfsscckosaraju

02

Intuition

💡

Two DFS passes. The first records finish times on the original graph; the last vertex to finish must sit in a 'source' component. Reversing every edge preserves each component internally but flips the one-way links between them — so a DFS on the reversed graph, started in finish-time order, can no longer escape a component. Each tree it grows is exactly one SCC.

03

Approach

1

Pass 1 — order by finish time

Run DFS on the original graph, pushing each vertex onto a stack when it finishes. Later finishers belong to components that come earlier in the condensed DAG.

2

Reverse the graph

Build the transpose: every u → v becomes v → u. Mutual reachability inside a component is unaffected, but the edges connecting different components now point the other way.

3

Pass 2 — DFS in reverse finish order

Pop vertices off the stack; each unvisited one starts a DFS on the reversed graph whose reachable set is precisely its SCC — the reversal blocks it from leaking into neighbouring components.

04

Solution & live demo

python

▶1def kosaraju(n, adj):
▶2    seen = [False] * n
▶3    order = []
▶4    def dfs1(v):                  # pass 1: record finish order
▶5        seen[v] = True
▶6        for u in adj[v]:
▶7            if not seen[u]: dfs1(u)
▶8        order.append(v)
▶9    for s in range(n):
▶10        if not seen[s]: dfs1(s)
▶11 
▶12    radj = [[] for _ in range(n)]  # reverse every edge
▶13    for u in range(n):
▶14        for v in adj[u]:
▶15            radj[v].append(u)
▶16 
▶17    seen2 = [False] * n
▶18    comps = []
▶19    def dfs2(v, comp):
▶20        seen2[v] = True
▶21        comp.append(v)
▶22        for u in radj[v]:
▶23            if not seen2[u]: dfs2(u, comp)
▶24    for v in reversed(order):     # pass 2: latest finish first
▶25        if not seen2[v]:
▶26            comp = []
▶27            dfs2(v, comp)
▶28            comps.append(comp)
▶29    return comps

05

Edge cases

Already strongly connected

Pass 2 finds one component containing everything.

DAG (no cycles)

Every vertex is its own component — V components.

Disconnected graph

Each piece contributes its own components; the outer loops cover all.

06

Complexity

Time

O(V + E)

Space

O(V + E)

Two DFS passes plus building the transpose.