Vibe Engines
YouTube

Vibe Engines is free, interactive AI engineering & system design — runs in your browser. Pick a learning path

Algorithms · Graphs

Watch Cycles Collapse Into Components.

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 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]?

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.

The picture: numbers, back edges and the stack

0d0l01d1l02d2l03d3l34d4l35d5l56d6l57d7l5SCC {0, 1, 2}SCC {3, 4}SCC {5, 6, 7}
The page’s directed graph: 8 nodes and 10 edges. Straight arrows are the tree edges DFS follows; the three curved arrows are back edges to a node still on the stack. Under each node, d is its discovery time and l its low-link. A node whose l equals its d (nodes 0, 3 and 5) is the root of a component, and the brackets show what gets popped when each root finishes.

Worked example, step by step

Run Tarjan on 0→1, 1→2, 2→0, 2→3, 3→4, 4→3, 4→5, 5→6, 6→7, 7→5, starting at node 0. Consecutive first visits are grouped into one row; the stack column is the stack after that step, bottom first.

StepEventWhat changesStack
1visit 0, 1, 2d0=l0=0, d1=l1=1, d2=l2=2[0 1 2]
2back edge 2→0l2 = min(l2, d0) = 0[0 1 2]
3visit 3, 4d3=l3=3, d4=l4=4[0 1 2 3 4]
4back edge 4→3l4 = min(l4, d3) = 3[0 1 2 3 4]
5visit 5, 6, 7d5=l5=5, d6=l6=6, d7=l7=7[0 1 2 3 4 5 6 7]
6back edge 7→5l7 = min(l7, d5) = 5[0 1 2 3 4 5 6 7]
7root 5: l5 = d5pop SCC {5, 6, 7}[0 1 2 3 4]
8root 3: l3 = d3pop SCC {3, 4}[0 1 2]
9root 0: l0 = d0pop SCC {0, 1, 2}[]

Three things to take from the trace. First, the low-link only changes on a back edge (steps 2, 4 and 6) and then flows up the recursion: when 7 finishes with l=5, node 6 and then node 5 fold that in; 5’s low stays equal to its own discovery time, which is what marks it as a root. Second, the components are popped in the order {5, 6, 7}, {3, 4}, {0, 1, 2}. That is reverse topological order of the condensation: a component is emitted only after every component it can reach, so the sink {5, 6, 7} comes out first. Third, the tree edge 2→3 leaves the component. Node 3’s component is popped and finished before 2 is, and when control returns to 2 it folds in l3=3, which is larger than l2=0 and changes nothing. Node 2 does not pull 3 into its component, because 3 cannot reach back to it.

Complexity and trade-offs

V is the number of nodes and E the number of edges; the graph on this page has V = 8 and E = 10.

CaseTimeSpaceWhy
TarjanO(V + E)O(V)One DFS. Each edge is looked at once (10 checks here) and each node is pushed and popped once. Extra memory is disc, low, the stack and the recursion depth.
KosarajuO(V + E)O(V + E)Two DFS passes, the second on the reversed graph, so it also has to build and hold that reversed copy.
Path-based (Gabow)O(V + E)O(V)Same single-pass idea with two stacks in place of low-link numbers.
Search from every nodeO(V · (V + E))O(V)Find what each node reaches, then compare. About 144 steps here against 18.
Transitive closureO(V³)O(V²)Floyd–Warshall style. 512 steps for 8 nodes, and it answers more than you asked.

Linear time is optimal, since every edge has to be read at least once. The practical trade-off between Tarjan and Kosaraju is memory and code shape: Tarjan never builds a reversed graph and finds components as it goes, but its correctness rests on subtle bookkeeping (disc versus low, on-stack or not), while Kosaraju is easier to prove and to explain. The real hazard is recursion depth. A simple path of 5,000 nodes already exceeds Python’s default recursion limit of 1,000, so production code on large graphs uses an explicit stack in place of recursion.

Common mistakes

  • Skipping the on-stack check

    A visited node is not the same as a node still in the current component. On 0→1, 1→0, 2→0 the right answer is [[0,1],[2]]. If the back-edge rule fires for any visited node, node 2 takes 0’s old discovery time, never looks like a root, and the result is [[0,1]]: node 2 disappears.

  • Forgetting to fold the child’s low-link

    Without low[v] = min(low[v], low[w]) after a tree-edge call, information from the subtree never reaches its ancestors. On this page’s graph you get [[0],[1,2],[3,4],[5],[6,7]] instead of three components.

  • Skipping the parent edge, as undirected algorithms do

    Bridge and articulation-point code ignores the edge back to the parent. In a directed graph that edge can be the cycle itself: on 0→1, 1→0 the correct answer is [[0,1]]; skipping the parent gives [[0],[1]].

  • Starting the DFS only from node 0

    Nodes unreachable from the start are never visited. On 4 nodes with edges 0→1, 2→3, 3→2 the right answer is [[0],[1],[2,3]]; a single DFS from 0 gives [[0],[1]]. Loop over every node and start where disc is still unset.

  • Recursing on a long chain

    A recursive DFS on a 5,000-node path raises RecursionError in Python at its default limit. Raise the limit with care, or write the DFS with an explicit stack of (node, next-neighbour-index) pairs.

Where this shows up

  • 2-SAT

    A 2-SAT formula is satisfiable exactly when no variable shares a component with its own negation in the implication graph, and the order Tarjan pops components in gives an assignment.

  • Dependency and import cycles

    Any component with more than one node is a cycle among modules, packages or build targets. Build tools and linters use component detection to report the cycle, then collapse each component to one node to get an order in which to build the rest.

  • Deadlock detection

    In a wait-for graph, where an edge means “this task is waiting for that one”, a component of two or more tasks is a set that can never proceed without outside help.

  • Structure of large graphs

    Studies of the web’s link graph describe a large strongly connected core with pages feeding into it and pages hanging off it; finding that core is this algorithm run at scale. Graph databases and analytics libraries expose component counts as a standard operation.

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
  1. Give every node two numbers: index — the order you first reached it — and low — the smallest index reachable from its subtree.
  2. Keep a stack of nodes whose component is not yet decided, plus an on_stack flag so you can test membership in O(1).
  3. For an unvisited neighbour: recurse, then low[v] = min(low[v], low[w]).
  4. 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.
  5. Use index[w] (not low[w]) for that back-edge case; the distinction is what keeps the invariant sound.
  6. 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.
CPython · WebAssembly

Keep going

Finished this one? 0 / 99 Algorithms done
NextBridges & Articulation Points: The Weak Links Next on the “What is connected to what” ladder · rung 5 of 5

Explore the topic

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

More Algorithms