Graph AlgosAlgorithmaka Tarjan strongly connected components, low-link SCC

Tarjan's SCC Algorithm

Find all strongly connected components in one DFS using discovery indices, low-link values and an explicit stack.

▶ VisualizePattern: Depth-First SearchPractice (2)
Progress

Overview

Tarjan's algorithm computes the Strongly Connected Components of a directed graph in a single DFS. Each vertex receives a discovery index (0, 1, 2, … in the order the DFS first reaches it) and a low value: the smallest index reachable from that vertex by walking down its DFS subtree and then following at most one edge to a vertex that is still on the algorithm's stack.

Vertices are pushed onto a stack when discovered and stay there until their whole SCC has been found. A vertex u with low[u] == index[u] is the root of an SCC: nothing in its subtree can reach anything discovered earlier, so everything above u on the stack (inclusive) is popped as one component.

Compared with Kosaraju's Algorithm it needs only one pass and no reversed graph, and the components come out in reverse topological order of the condensation (a sink component is emitted first), which is exactly what DAG-style DP over components wants.

directedSCClow-linkDFSsingle passO(V + E)

Intuition

A mental model before the formal terms.

Imagine the DFS as descending a cave system, numbering each chamber as you enter it (index). While exploring, you sometimes find a passage leading back up to a chamber you are still inside (a back edge). low[u] answers "what is the highest chamber I can climb back to from anywhere below u?". If the answer is u itself, then u and everything below it that has not already been sealed off form a closed pocket — an SCC — and you seal it by popping the stack down to u.

Tiny example: edges 0→1, 1→2, 2→0, 2→3. DFS gives indices 0,1,2,3. Vertex 3 has no outgoing edges: low[3] = 3 = index[3], so {3} is popped as an SCC. Back at 2: the edge 2→0 reaches index 0 which is on the stack, so low[2] = 0. That propagates up: low[1] = 0, low[0] = 0. Only at 0 does low == index, so {0, 1, 2} is popped as one SCC.

How it works

  1. Initialise index[v] = -1 for all v (undiscovered), an empty stack, a boolean onStack[v], and a counter.
  2. Visit u: set index[u] = low[u] = counter++, push u, mark onStack[u].
  3. For each edge u → v: if v is undiscovered, recurse into v, then low[u] = min(low[u], low[v]) (tree edge — inherit whatever the subtree can climb to). Else if onStack[v], low[u] = min(low[u], index[v]) (back/cross edge to a vertex whose SCC is not yet closed). Else v belongs to an already-emitted SCC — ignore it.
  4. After scanning all edges of u, if low[u] == index[u], pop the stack until u comes off; the popped vertices are one SCC. Assign them a component id.
  5. Repeat from every undiscovered vertex so that all DFS trees are covered.
  6. The update low[u] = min(low[u], index[v]) for back edges (not low[v]) is enough for SCCs; using low[v] also works here but is *wrong* for Bridges, so keep the habit of using index[v].

Why it works

Claim: at the moment u finishes, the vertices on the stack above u are exactly the vertices of u's DFS subtree whose SCC has not been emitted yet. Every vertex is pushed on discovery and only popped as part of an SCC, so the stack contains completed-but-unsealed subtrees.

If low[u] == index[u], no vertex in u's open subtree can reach a vertex discovered before u that is still open. So the subtree cannot escape upward, and since every vertex in it is reachable from u (tree paths) and can reach u (otherwise its own low would have closed it earlier), they are all mutually reachable — an SCC with root u.

If low[u] < index[u], then some vertex in the subtree reaches an open ancestor a, and a reaches u via tree edges, so u's SCC contains a and is not complete yet; correctly, nothing is popped.

Ignoring edges to vertices that are *not* on the stack is safe: those vertices belong to SCCs that are already sealed, and nothing in a sealed SCC can reach back into an open one (the condensation is a DAG and DFS emits sinks first).

Recognition

How to tell a problem wants this.

  • Directed graph, need SCCs, and you want a single pass or the components in reverse topological order.
  • You are also computing something else in the same DFS (e.g. per-vertex DP over the condensation) — Tarjan integrates naturally.
  • Memory is tight: no reversed copy of the graph is needed.
“connected groups” → Depth-First Search

Interactive visualization

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

ABCDEFGH
Stack (top → bottom)
empty
SCCs found
empty
1/29Tarjan runs one DFS. Each node gets a discovery index and a low-link; when they coincide the node roots an SCC, which is exactly what sits above it on the stack.
Current node (label = idx/low)On the stackIn a completed SCCDFS tree edgeBack edge lowering low
PseudocodeLearn Tarjan's SCC Algorithm →
1index = 0; stack = []
2def strongconnect(u):
3  idx[u] = low[u] = index; index += 1; stack.push(u); onStack[u] = true
4  for v in neighbors(u):
5    if v unvisited: strongconnect(v); low[u] = min(low[u], low[v])
6    elif onStack[v]: low[u] = min(low[u], idx[v])
7  if low[u] == idx[u]:
8    pop stack down to u → one SCC
9for u in nodes: if u unvisited: strongconnect(u)
Complexity
best O(V + E)
avg O(V + E)
worst O(V + E)
space O(V)
Speed

Pseudocode

1index[*] = -1; counter = 0; stack = []
2dfs(u):
3  index[u] = low[u] = counter++; push u; onStack[u] = true
4  for v in adj[u]:
5    if index[v] == -1: dfs(v); low[u] = min(low[u], low[v])
6    else if onStack[v]: low[u] = min(low[u], index[v])
7  if low[u] == index[u]:
8    pop until u; emit popped vertices as one SCC
9for u in 0..n-1: if index[u] == -1: dfs(u)

Implementations

1import sys
2 
3 
4def tarjan_scc(n: int, adj: list[list[int]]) -> list[list[int]]:
5    """Return the SCCs of a directed graph, each as a list of vertices.
6    Components are emitted in reverse topological order of the condensation."""
71 · Initialise per-vertex state
8    sys.setrecursionlimit(max(10_000, 2 * n + 100))
9    index = [-1] * n
10    low = [0] * n
11    on_stack = [False] * n
12    stack: list[int] = []
13    sccs: list[list[int]] = []
14    counter = 0
15 
16    def dfs(u: int) -> None:
17        nonlocal counter
182 · Discover u: index, low, push
19        index[u] = low[u] = counter
20        counter += 1
21        stack.append(u)
22        on_stack[u] = True
23 
243 · Scan edges, update low-link
25        for v in adj[u]:
26            if index[v] == -1:
27                dfs(v)
28                low[u] = min(low[u], low[v])
29            elif on_stack[v]:
30                low[u] = min(low[u], index[v])
31 
324 · Root of an SCC: pop down to u
33        if low[u] == index[u]:
34            comp: list[int] = []
35            while True:
36                v = stack.pop()
37                on_stack[v] = False
38                comp.append(v)
39                if v == u:
40                    break
41            sccs.append(comp)
42 
435 · Cover every DFS tree
44    for u in range(n):
45        if index[u] == -1:
46            dfs(u)
47    return sccs
Walkthrough
  1. sys.setrecursionlimit is raised to at least 2n + 100 because the DFS may nest n deep.
  2. nonlocal counter lets the nested function increment the outer integer; lists need no declaration because they are mutated in place.
  3. Tree edges propagate low[v]; on-stack edges use index[v].
  4. A while True loop pops until u is removed, then the component is appended.
  5. The outer loop seeds a DFS from every undiscovered vertex.
Complexity (this implementation)
time O(V + E) · space O(V)

Raising the recursion limit does not enlarge the C stack: beyond ~10^5 frames CPython can still segfault. Use the iterative alternative.

Language notes
  • sys.setrecursionlimit only raises the interpreter guard; the OS thread stack is the real limit (threading.stack_size can help).
  • The iterative alternative keeps (vertex, next_index) frames in a list.
  • Python 3.11+ recursion is faster, but still ~50x slower per frame than C++.
Common mistakes in this language
  • Forgetting nonlocal counter — the inner function raises UnboundLocalError.
  • Using low[v] for on-stack edges.
  • Running the recursive version on a 10^5-long path without adjusting the recursion limit.
Language differences that matter here
  • Recursion depth: Python defaults to 1000 frames (raise with sys.setrecursionlimit, but the C stack still caps around 10^5); JS/TS ~10k frames in V8; C++ ~10^5 with an 8 MB stack. All four ship an iterative alternative.
  • C++ groups the state in a class; JS/TS/Python use closures over arrays and Python needs nonlocal for the integer counter.
  • C++ vector<bool> is bit-packed; JS/TS/Python boolean arrays are regular arrays.

Complexity

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

Recursion depth can reach V; use an iterative DFS for very deep graphs in Python/JS.

Compare growth rates in the Complexity Explorer →

When to use — and when not to

Use it when
  • You need SCCs in one pass, or in reverse topological order (sink components first) for DP on the condensation.
  • Memory matters — no reversed graph copy is needed.
  • You already have a DFS framework and want to add low-link bookkeeping (the same skeleton gives Bridges and Articulation Points on undirected graphs).
Avoid it when
  • You want the easiest-to-explain algorithm in an interview — Kosaraju's Algorithm has a shorter correctness argument, at the cost of a second pass.
  • Undirected graph — every connected component is strongly connected; use Connected Components.
  • Extremely deep graphs in a language without tail recursion and with a small stack — convert to iterative DFS or use Kosaraju with iterative passes.

Alternatives

Kosaraju's AlgorithmConnected ComponentsCycle Detection
Compare: Tarjan vs Kosaraju

Common mistakes

  • Updating low[u] from a vertex that is not on the stack — that vertex belongs to a finished SCC and must be ignored; otherwise components get merged incorrectly.
  • Forgetting to clear onStack[v] when popping an SCC.
  • Emitting the component without popping down to and including u, or popping one too many.
  • Assuming component ids are in topological order — Tarjan emits sinks first; reverse the list if you need sources first.

Interview patterns

  • Compute SCC ids, build the condensation and count source / sink components.
  • 2-SAT: build the implication graph, run Tarjan, and check comp[x] != comp[not x]; the topological order of components gives the assignment.
  • Detect whether every vertex lies on a cycle: each SCC must have size > 1 or a self-loop.
Interview questions on this
Mock interviews

Example problems

Critical Connections in a NetworkhardCourse Schedulemedium