Home/Graphs/Tarjan SCC
Search algorithmsCTRL K

Tarjan SCC

· strongly connected components · one DFS
/graphs/tarjan-scc
COMPONENTS
0
found so far
VISITED
0/ 10
nodes given an index
ON STACK
0
waiting for their root
INDEX
0
next DFS number
LARGEST
0
nodes in the biggest component
currenton the stack · tree edgeback edgein a component
10 nodes · 14 edges · seed 7 · 39 steps
step 0 / 38
Nodes10
tarjan_scc.ts
1
function tarjan(graph: Graph) {
2
  let index = 0; const stack: Node[] = []; const onStack = new Set<Node>();
3
  const indexOf = new Map<Node, number>(), lowLink = new Map<Node, number>(); const components: Node[][] = [];
4
  const visit = (node: Node) => {
5
    indexOf.set(node, index); lowLink.set(node, index); index++;
6
    stack.push(node); onStack.add(node);
7
    for (const next of graph.successors(node)) {
8
      if (!indexOf.has(next)) { visit(next); lowLink.set(node, Math.min(lowLink.get(node)!, lowLink.get(next)!)); }
9
      else if (onStack.has(next)) lowLink.set(node, Math.min(lowLink.get(node)!, indexOf.get(next)!));
10
    }
11
    if (lowLink.get(node) === indexOf.get(node)) {
12
      const component: Node[] = [];
13
      let top: Node; do { top = stack.pop()!; onStack.delete(top); component.push(top); } while (top !== node);
14
      components.push(component);
15
    }
16
  };
17
  for (const node of graph.nodes) if (!indexOf.has(node)) visit(node);
18
  return components;
19
}
CURRENT STEP
line 17

A is unvisited: start a depth-first search there.

// how it works

Understanding Tarjan SCC

Tarjan · index and low link: a node whose low link is itself closes a component
01

The idea

A strongly connected component is a set of nodes that can all reach each other. Tarjan finds them in a single depth-first search by giving every node an index in visit order and a low link: the smallest index reachable from it through its DFS subtree plus at most one back edge. Visited nodes stay on a stack until their component is complete.

When the search returns to a node whose low link still equals its own index, nothing below it reaches back above it, so it is the root of a component: everything on the stack down to it is popped as one component. The label under each node shows index / low link.

02

The four stages

1
visitindex ← low ← counter; push on the stack
2
descendtree edge: recurse, then low ← min(low, low of child)
3
back edgeto a node on the stack: low ← min(low, its index)
4
closelow = index: pop the stack down to here
03

Complexity

best
O(V + E)every node and edge once
average
O(V + E)a single DFS
worst
O(V + E)the same
space
O(V)index, low link and the stack
04

Versus its siblings

EDGE VISITS · 1 000 NODES, 3 000 EDGES
tarjan
4,000
kosaraju
8,000
naive (bfs per node)
4M
Kosaraju visits every edge twice, once per direction
05

Pseudocode

TARJAN(graph)
  VISIT(node): index[node] ← low[node] ← counter++; push node
    for each successor: unvisited → VISIT it, low[node] ← min(low[node], low[successor]); on the stack → low[node] ← min(low[node], index[successor])
    if low[node] = index[node]: pop the stack down to node, that is one component
  VISIT every unvisited node
06

When to use

Condensing a directed graph into a DAG of components: dependency cycles in a build, 2-SAT, deadlock detection.
Any time a single pass over a directed graph is required; Tarjan's low link trick also gives bridges and articulation points.
07

Pitfalls

Cross edges to finished components must be ignored; updating low link from them breaks the invariant.
The recursion depth is the longest DFS path; big graphs need an explicit stack.
Components come out in reverse topological order of the condensation, which is often exactly what the next step needs.
08

History

Robert Tarjan published the algorithm in 1972 in the same paper that made depth-first search a first-class tool, alongside linear-time biconnectivity. It remains the reference SCC algorithm; Gabow's path-based variant from 2000 replaces low links with a second stack.

Back to Graphs