Graph AlgosAlgorithmaka Kosaraju-Sharir, two-pass SCC

Kosaraju's Algorithm

Find strongly connected components with two DFS passes: record finish order, then DFS the reversed graph in decreasing finish time.

▶ VisualizePattern: Depth-First SearchPractice (2)
Progress

Overview

Kosaraju's algorithm computes Strongly Connected Components with two plain depth-first searches. Pass 1 runs Depth-First Search (DFS) on the original graph and records vertices in finish order (post-order). Pass 2 builds the reverse graph G^T (every edge u → v becomes v → u) and runs DFS from vertices in decreasing finish time. Each DFS tree of pass 2 is exactly one SCC.

It is slightly slower than Tarjan's SCC Algorithm in practice (two traversals, plus building the reversed adjacency list) but the code is two ordinary DFS routines and the proof is short, which makes it a favourite for interviews and for iterative implementations.

Components are produced in topological order of the condensation: the first component found is a source component (nothing outside it points into it).

directedSCCreverse graphtwo passesO(V + E)

Intuition

A mental model before the formal terms.

Reversing all edges does not change which vertices are mutually reachable — a round trip u → … → v → … → u reversed is still a round trip. But reversal flips the direction of travel *between* components. If, in the original graph, you can go from component A to component B, then in the reversed graph you can go from B to A only.

Pass 1 finds a vertex that finishes last; it lives in a component with no incoming edges from unfinished components — a "source" of the condensation. In the reversed graph a source becomes a sink: DFS from it cannot leak into any other component, so it paints exactly one SCC. Remove it (mark visited) and the next-latest finisher is again a source among what remains. Repeat.

Tiny example: edges 0→1, 1→2, 2→0, 2→3. Pass 1 from 0 finishes 3 first, then 2, 1, 0; finish order [3, 2, 1, 0]. Reversed graph edges: 1→0, 2→1, 0→2, 3→2. Pass 2 starts at 0 (finished last): reaches 2 and 1 but not 3 (edge 3→2 points the wrong way) — SCC {0, 1, 2}. Then 3: SCC {3}.

How it works

  1. Pass 1: for every unvisited vertex run DFS on G; when a vertex finishes (all neighbours explored), append it to order.
  2. Build radj: for each edge u → v in G, add u to radj[v].
  3. Pass 2: iterate order from the end (latest finisher first). For each vertex not yet assigned a component, run DFS on radj, assigning every reached vertex the current component id, then increment the id.
  4. Return comp[v] (ids are in topological order of the condensation) and/or the list of components.

Why it works

Key lemma: if there is an edge from SCC A to SCC B in G, then the maximum finish time in A is larger than the maximum finish time in B. Either DFS enters A first and then finishes all of B inside that call (so A's root finishes later), or it enters B first and cannot reach A (no B → A path, else they would be one SCC), so all of B finishes before A is even discovered.

Therefore the vertex with the largest finish time overall lies in a source SCC of the condensation. In G^T that SCC is a sink, so DFS from that vertex reaches its own SCC (mutual reachability is preserved by reversal) and nothing else.

Induction: after removing the found SCC, the largest remaining finish time again identifies a source among the remaining components, and the reversed DFS again stays inside it because previously found components are marked visited.

Recognition

How to tell a problem wants this.

  • Directed graph, need SCCs, and you prefer two simple DFS routines over low-link bookkeeping.
  • Components must come out in topological order (sources first) — Kosaraju gives that directly.
  • You already need the reversed graph for something else (e.g. "which vertices can reach t").
“connected groups” → Depth-First Search

Interactive visualization

Play, step, change the input. ← → and space work too.

ABCDEFGH
Finish order (first → last)
empty
SCCs found
empty
1/33Kosaraju needs two passes. Pass 1 runs DFS on G to compute finishing times; pass 2 runs DFS on the transposed graph in decreasing finish order.
Current nodeOn recursion pathFinished in pass 1 (label = finish rank)SCC (odd)SCC (even)DFS tree edge
PseudocodeLearn Kosaraju's Algorithm →
1order = []; visited = {}
2for u in nodes: if u unvisited: dfs1(u)   # append u to order after its neighbors
3GT = transpose(G)   # reverse every edge
4visited = {}
5for u in reversed(order):
6  if u unvisited in GT: dfs2(u) collects one SCC
7return SCCs
Complexity
best O(V + E)
avg O(V + E)
worst O(V + E)
space O(V + E)
Speed

Pseudocode

1order = []; visited[*] = false
2dfs1(u): visited[u] = true; for v in adj[u]: if !visited[v]: dfs1(v); order.append(u)
3for u in 0..n-1: if !visited[u]: dfs1(u)
4radj = reverse of adj
5comp[*] = -1; c = 0
6dfs2(u): comp[u] = c; for v in radj[u]: if comp[v] == -1: dfs2(v)
7for u in reversed(order): if comp[u] == -1: dfs2(u); c += 1
8return comp   # c components, ids in topological order

Implementations

1def kosaraju(n: int, adj: list[list[int]]) -> list[int]:
2    """Return comp[v] = SCC id of v. Ids are in topological order of the
3    condensation. Both passes are iterative, so deep graphs are safe."""
41 · Pass 1: iterative post-order records the finish order
5    visited = [False] * n
6    order: list[int] = []
7    for s in range(n):
8        if visited[s]:
9            continue
10        visited[s] = True
11        frames = [(s, 0)]  # (vertex, next neighbour index)
12        while frames:
13            u, i = frames[-1]
14            if i < len(adj[u]):
15                frames[-1] = (u, i + 1)
16                v = adj[u][i]
17                if not visited[v]:
18                    visited[v] = True
19                    frames.append((v, 0))
20            else:
21                order.append(u)
22                frames.pop()
23 
242 · Build the reversed graph
25    radj: list[list[int]] = [[] for _ in range(n)]
26    for u in range(n):
27        for v in adj[u]:
28            radj[v].append(u)
29 
303 · Pass 2: scan vertices in decreasing finish time
31    comp = [-1] * n
32    c = 0
33    for s in reversed(order):
34        if comp[s] != -1:
35            continue
36 
374 · Flood-fill one SCC on the reversed graph
38        comp[s] = c
39        stack = [s]
40        while stack:
41            u = stack.pop()
42            for v in radj[u]:
43                if comp[v] == -1:
44                    comp[v] = c
45                    stack.append(v)
46        c += 1
47    return comp
Walkthrough
  1. Pass 1 keeps (vertex, next_index) tuples; since tuples are immutable, advancing the cursor rewrites the top frame with frames[-1] = (u, i + 1).
  2. Appending to order when the frame pops reproduces recursive post-order without recursion.
  3. radj is built with a list comprehension of independent lists, then one pass over all edges.
  4. for s in reversed(order) iterates lazily from the back — no copy of the list.
  5. Each flood fill labels exactly one SCC; c counts components in condensation-topological order.
Complexity (this implementation)
time O(V + E) · space O(V + E)
Language notes
  • Both passes are iterative, so sys.setrecursionlimit is not needed; a recursive version dies at ~1000 frames by default and risks a C-stack crash even when raised.
  • reversed(order) returns an iterator over the existing list — O(1) extra space, unlike order[::-1] which copies.
  • A mutable list frame ([s, 0] with frames[-1][1] += 1) works too; the tuple version trades one allocation per step for immutability.
Common mistakes in this language
  • Writing u, i = frames[-1] and then mutating the local i — locals do not write back; you must reassign frames[-1].
  • Using order.pop() in pass 2 while also indexing it — pick one traversal style.
  • Building radj as [[]] * n, aliasing a single list.
Language differences that matter here
  • Frame mutation differs: C++ mutates through structured-binding references, JS/TS mutate the array element top[1]++, Python must reassign the tuple (or use a list frame) because tuples are immutable.
  • All four are fully iterative — unlike the Tarjan entry, no recursion-limit tuning is needed in any language.
  • C++ returns vector<int>; JS/TS return number[]; Python returns list[int] — all use comp-label form rather than lists of vertices, since Kosaraju is usually a preprocessing step.

Complexity

Best
O(V + E)
Average
O(V + E)
Worst
O(V + E)
Space
O(V + E)

Extra O(V + E) memory for the reversed adjacency list; roughly 2× the work of Tarjan.

Compare growth rates in the Complexity Explorer →

When to use — and when not to

Use it when
  • You want the simplest provably correct SCC routine and can afford a second pass and a reversed copy of the graph.
  • Components are needed in topological order (sources first).
  • Iterative implementation is required — two independent DFS passes are easy to make stack-free.
Avoid it when
  • Memory-constrained settings where the reversed adjacency list is too expensive — use Tarjan's SCC Algorithm.
  • You need low-link values anyway (e.g. also computing bridges) — Tarjan shares that machinery.
  • Undirected graphs — use Connected Components.

Alternatives

Tarjan's SCC AlgorithmConnected Components
Compare: Tarjan vs Kosaraju

Common mistakes

  • Recording pre-order (discovery) instead of post-order (finish) in pass 1 — the ordering lemma only holds for finish times.
  • Running pass 2 on the original graph instead of the reversed one, or iterating the finish order forwards instead of backwards.
  • Building the reversed graph incorrectly for the adjacency-list representation (adding v to radj[u] instead of u to radj[v]).
  • Recursive pass 1 overflowing the stack on long paths in Python/JavaScript — use the explicit (vertex, nextIndex) stack.

Interview patterns

  • Compute SCC ids, then answer "is the graph strongly connected?" (exactly one id).
  • Condense and count source components to find the minimum number of starting vertices needed to reach everything.
  • Explain the reverse-graph idea in words: "reversing keeps SCCs intact but flips the DAG of components, so the last finisher becomes a sink".
Interview questions on this
Mock interviews

Example problems

Critical Connections in a NetworkhardCourse Schedulemedium