On a directed graph, "connected" splits into two different questions. Can you get from A to B at all, following arrows in whatever direction they point, is one — that's ordinary reachability. Can you get from A to B and back again, using only arrows in their actual direction, is a stricter one. A strongly connected component (SCC) is a maximal group of nodes where every pair satisfies the stricter question: some directed path leads from each node to every other node in the group. Think of a map of one-way streets — an SCC is a neighborhood you can loop around and return to your starting corner from anywhere inside it, without ever driving against traffic.
Topological sort already showed that a three-state depth-first search (unvisited, still-on-the-current-path, finished) can tell whether a directed graph has any cycle at all. Tarjan's algorithm asks a sharper question — not just "is there a cycle," but "group every node into exactly the set of other nodes it's mutually reachable with" — and answers it with one more piece of bookkeeping layered onto that same single DFS pass: for every node, the earliest discovery time reachable from it by following tree edges down and then at most one back edge up to a node still in progress. That number is called its low-link value, and the moment a node's low-link equals its own discovery time, everything still sitting "in progress" below it on an explicit stack forms one complete SCC.
Eight intersections, A through H, joined by one-way streets. Press
Step or Run to walk Tarjan's algorithm: a dashed node is pushed
onto the stack and still "in progress" (on the current DFS path, not yet resolved into a
component); a filled node is closed — finalized into a component and popped off
the stack for good. The three strips below the graph track the algorithm's actual state:
discovery/low-link numbers per node, the explicit stack itself (closest to being finalized is on
the right), and the components found so far, in the order they closed.
Every node gets pushed onto an explicit stack the moment it's first discovered, and stays there
for as long as it's "in progress" — meaning some node still being explored might yet find a path
back to it. disc[u] is simply the order nodes are discovered in, a plain counter.
low[u] starts equal to disc[u] and can only shrink, and it shrinks in
exactly two situations: when a tree edge to an unvisited neighbor v returns with a
smaller low[v], or when an edge lands directly on a neighbor v that's
still on the stack — a back edge onto u's own current DFS path — in which
case low[u] can drop as far as disc[v]. Both cases mean the same thing:
something reachable from u can reach further back up the stack than u
itself can claim credit for alone, so u can't yet be finalized on its own.
The invariant that makes the algorithm work: when low[u] === disc[u], nothing in
u's subtree has found a path back above u on the stack. That means every
node still on the stack from u upward — u itself and everything pushed
after it that hasn't already been popped into an earlier component — is mutually reachable through
u, and none of them can reach anything outside that group without also
coming back through u. Popping the stack down to and including u
produces exactly one complete SCC, and u is called that component's root.
Matches the demo above one for one — the demo's step generator is this same recursive shape
with yield points added at each state transition:
function stronglyConnectedComponents(numNodes, adjacency) {
const disc = new Array(numNodes).fill(-1);
const low = new Array(numNodes).fill(-1);
const onStack = new Array(numNodes).fill(false);
const stack = [];
const sccs = [];
let time = 0;
function strongconnect(u) {
disc[u] = low[u] = time++;
stack.push(u);
onStack[u] = true;
for (const v of adjacency[u]) {
if (disc[v] === -1) {
strongconnect(v);
low[u] = Math.min(low[u], low[v]);
} else if (onStack[v]) {
// back edge onto the current DFS path — NOT any already-visited node,
// see Pitfalls for what goes wrong if this check is dropped
low[u] = Math.min(low[u], disc[v]);
}
// else: v is visited and already fully resolved into an earlier
// component — a cross edge, irrelevant to u's own low-link
}
if (low[u] === disc[u]) {
const component = [];
let w;
do {
w = stack.pop();
onStack[w] = false;
component.push(w);
} while (w !== u);
sccs.push(component);
}
}
for (let u = 0; u < numNodes; u++) {
if (disc[u] === -1) strongconnect(u);
}
return sccs;
}The "still on the stack" check isn't optional — it's the whole algorithm. It's
tempting to simplify the neighbor loop to "if v is already visited, pull
low[u] down to disc[v]," dropping the onStack[v] check
entirely. That's wrong, and the demo's own graph shows exactly how: when G examines
its edge to H, H has already been visited and closed into its
own component — a cross edge to an unrelated, already-finished part of the graph, not a path back
onto G's own stack. Folding disc[H] into low[G] anyway
drags low[G] down to 4, below its own disc[G] = 5, so
G never gets recognized as a component root when it should. G and
F are left dangling on the stack, and when C closes shortly after, it
sweeps them up too — producing one wrong four-node component {C, D, F, G} where two
correct two-node components, {C, D} and {F, G}, should have closed
separately. Checked directly: running the buggy version (no onStack check) against
this exact page's graph reproduces that merge, not just a hypothetical one.
Components close in reverse topological order of the condensation. Collapse
each SCC down to a single node and every remaining edge into a DAG — that's the graph's
condensation. On this page's graph, collapsing gives four nodes:
{A,B,E} → {C,D} → {F,G} → {H} (reading arrows left to right). Watch the order
components actually close in the demo above: {H} first, then {F,G}, then
{C,D}, then {A,B,E} last — the exact reverse. This isn't a coincidence:
a component can't close until everything reachable from it has already closed, which means sinks
of the condensation finish first and sources finish last, every time. It's the same
"finish-order-then-reverse" shape topological
sort relies on, one level up — Tarjan's own closing order is already a topological sort of the
condensation graph, just discovered back-to-front.
A node doesn't need a self-loop to be its own component. H in the
demo happens to have a self-loop (H → H), but that's not what makes
{H} a valid singleton SCC — a single node is trivially reachable from itself by a
path of zero edges, so any node with no cycle back to itself is still its own one-node SCC. The
self-loop here is a genuine edge case worth having in the demo (it immediately satisfies
low[H] === disc[H] via the onStack[H] check on itself), not a
requirement for singleton components in general.
This is strictly about directed edges. An undirected graph's notion of
"connected component" — can you get from A to B ignoring arrow direction entirely — is a much
simpler question, answered by plain DFS/BFS or by Union-Find processing edges one at a time. Strongly
connected components only exist as a distinct idea because direction matters: D → H
means the trip from Data Structures corner to the far edge of town is one-way, and no amount of
other reachability makes the return trip free.
Deep graphs can still overflow the call stack. The recursive shape above has
the same limitation as any deep recursive DFS — a long chain of nodes can exceed the language's
call-stack limit. See DFS's own Pitfalls for why, and
why an iterative version with an explicit stack sidesteps it; the same rewrite applies here, just
with the extra low/onStack bookkeeping carried alongside each explicit
frame instead of each recursive call.
Time: O(V + E) — one DFS pass, identical to plain DFS: every
vertex is visited and closed exactly once, and every edge is inspected exactly once, from its
source. Space: O(V) for disc, low,
onStack, the explicit component stack, and the recursion depth.
This site's guide, Choosing a Graph Traversal Approach, compares this entry against the other ten Graph Traversal entries side by side.