In a directed graph, which nodes can all reach each other? Each such maximal group is a strongly connected component. Tarjan's algorithm finds every one in a single depth-first pass — carrying two numbers per node, a discovery time and a low-link — and pops a whole component off a stack the instant it finds the cycle's root. O(V+E).
O(V+E) · one DFS pass · directed graphs
disc[v]
The order DFS first reached v — its discovery time.
low[v]
The smallest disc reachable from v via tree edges + one back edge.
the stack
Nodes visited but not yet assigned to a component wait here.
the root
When low[v] == disc[v], v roots an SCC — pop down to it.
tarjan.js — one DFS, two numbers, one stack
Ready
DFS walks the graph, stamping each node with a discovery time and a low-link. Press Step: tree edges (green) recurse; back edges (red) to a node still on the stack pull the low-link down. When a node's low equals its disc, it's a component root — pop the stack down to it and paint the SCC.
–
at node
0
on stack
0
SCCs found
How it works
The whole algorithm hinges on the low-link. As DFS descends, each node remembers the earliest-discovered node it can still reach without leaving the current recursion — that's low. A node that can loop back to an ancestor inherits that ancestor's small number; a node that can't stays equal to its own discovery time and is therefore a component's entry point.
1
Visit and stamp
On first reaching v, set disc[v] = low[v] = time++ and push v on the stack. It stays there until its whole component is known.
2
Recurse, then absorb
For a tree edge v→w, recurse into w, then low[v] = min(low[v], low[w]) — v inherits anything w could reach.
3
Back edges pull low down
If w is already on the stack, low[v] = min(low[v], disc[w]) — v can loop back to an earlier node, so it belongs to that cycle.
✓
Root found → pop a component
After exploring v, if low[v] == disc[v], pop the stack down to and including v — those nodes are exactly one SCC.
Time
O(V + E)
Space
O(V)
Passes
1 DFS
vs Kosaraju
2 DFS
The code
def tarjan(v):
disc[v] = low[v] = time[0]; time[0] += 1
stack.append(v); on_stack[v] = True
for w in adj[v]:
if disc[w] == -1: # tree edge
tarjan(w)
low[v] = min(low[v], low[w])
elif on_stack[w]: # back edge to live node
low[v] = min(low[v], disc[w])
if low[v] == disc[v]: # v roots an SCCwhile True:
w = stack.pop(); on_stack[w] = False
comp[w] = scc_id
if w == v: break
scc_id += 1
Note the two different mins: a tree edge folds in the child's low (everything the subtree can reach), but a back edge uses the target's disc, not its low — you may only claim to reach a node that's still on the stack, i.e. still part of the component under construction. Get that distinction wrong and separate components merge. Collapsing each SCC to a point gives the condensation, a DAG used for 2-SAT, dependency cycles, and dead-code analysis.
Quick check
1. What does low[v] == disc[v] tell you?
Right — v's low-link never dropped below its own discovery time, so nothing it reaches loops back above it. v is the entry point of its component; everything above it on the stack, down to v, is that SCC.
2. On a back edge v→w with w on the stack, why use disc[w] and not low[w]?
Right — using low[w] could pull in a discovery time from a node that has already left the stack (a different component), wrongly merging SCCs. The back edge only proves you can reach w, so use disc[w].
FAQ
What is a strongly connected component?
A maximal set of nodes in a directed graph where every node can reach every other by following edges. Collapse each to a point and you get a DAG, the condensation.
What is the low-link?
The smallest discovery time reachable from a node using tree edges plus at most one back edge to a node still on the stack.
Why is it O(V+E)?
A single DFS visits every node and traverses every edge exactly once; the stack work is amortized O(1) per node.
How does it compare to Kosaraju's?
Kosaraju's runs two DFS passes (one on the transpose graph); Tarjan's needs just one, which is often faster in practice.
SOLVE IT YOURSELF
Solve it: find the strongly connected components
Which groups of nodes can all reach each other? Tarjan answers it in a single depth-first pass, using nothing but two numbers per node. Python or TypeScript, running for real in your browser.
YOUR TASK
Implement scc_components(n, edges): given a directed graph, return the strongly connected components as a sorted list of sorted vertex lists (sorted so the result is deterministic and comparable).
HINTS — 6 IDEAS
Give every node two numbers: index — the order you first reached it — and low — the smallest index reachable from its subtree.
Keep a stack of nodes whose component is not yet decided, plus an on_stack flag so you can test membership in O(1).
For an unvisited neighbour: recurse, then low[v] = min(low[v], low[w]).
For an already-visited neighbour: only pull in its value if it is still on the stack. Skipping that check is the classic bug — it merges separate components that merely point at each other.
Use index[w] (not low[w]) for that back-edge case; the distinction is what keeps the invariant sound.
When low[v] == index[v], v is the root of a component: pop the stack down to and including v, and that is one SCC.