What are discovery time and low-link?

Discovery time is the order in which DFS first visits a node. A node's low-link is the smallest discovery time reachable from it using tree edges plus at most one back edge to a node still on the stack. When a node's low-link equals its own discovery time, it is the root of an SCC.

Why pop the stack when low-link equals discovery time?

A node whose low-link never dropped below its discovery time cannot reach any earlier node still being processed — so it's the entry point (root) of its component. Every node above it on the stack, down to it, forms exactly one SCC, so they're popped together.

How fast is Tarjan's algorithm?

O(V + E) time — a single depth-first search visits each node and edge once — and O(V) extra space for the stack and the two arrays. It finds all strongly connected components in one pass, which is why it's preferred over the two-pass Kosaraju's algorithm in many settings.

Algorithms · Graphs

Watch Cycles Collapse Into Components.

Q: What is a strongly connected component?

In a directed graph, a strongly connected component (SCC) is a maximal set of nodes where every node can reach every other node in the set by following edge directions. Collapsing each SCC to a single point yields a directed acyclic graph called the condensation.

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

on stack

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.

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.

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.

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 SCC while 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?

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.

Keep going

Finished this one? 0 / 62 Algorithms done

Explore the topic

See this alongside everything else on the same subject — handbooks, system designs, challenges and tools, in one place.

Algorithms & DSA

Watch Cycles Collapse Into Components.

How it works

Visit and stamp

Recurse, then absorb

Back edges pull low down

Root found → pop a component

The code

Quick check

FAQ

Keep going

Explore the topic

More Algorithms

Explore more from Vibe Engines

How it works

Visit and stamp

Recurse, then absorb

Back edges pull low down

Root found → pop a component

The code

Quick check

FAQ

Keep going

DFS & Topological Sort →

BFS & Flood Fill →

Kruskal's MST →

The DSA Roadmap →

Explore the topic

More Algorithms

Explore more from Vibe Engines

Get the next one in your inbox.