Strongly Connected Components

The 10-second versionCopy Anchor Link

In a directed graph, two vertices are strongly connected if each can reach the other. A strongly connected component (SCC) is a maximal set of vertices that are all mutually reachable — a tight clique of mutual reachability. Every directed graph splits cleanly into SCCs, and if you shrink each SCC to a single node, the result is always a DAG (no cycles). Tarjan's algorithm finds every SCC in one DFS with a stack and a "lowlink" number; Kosaraju's method does it with two DFS passes on the graph and its transpose. Both run in O(V + E).

Why this existedCopy Anchor Link

Directed graphs are everywhere — call graphs, dependency graphs, state machines, web links — and their defining feature is that reachability is not symmetric. From A you might reach B without B reaching A. The only places symmetry holds are the cyclic knots: groups of vertices that can all reach each other.

Those knots matter enormously. A file that (transitively) imports itself through a cycle of modules, a set of functions that call each other in a loop, a formula where variable x and its negation become entangled — these are all "mutual reachability" questions. Pin down the SCCs and you've pinned down the feedback structure of the whole graph.

• 1960s — strong connectivity is recognized as a fundamental property of digraphs, but the natural test ("can u reach v and v reach u?") is expensive to run for every pair.
• 1972 — Robert Tarjan publishes "Depth-first search and linear graph algorithms," giving a single-DFS, O(V + E) algorithm using discovery times and a lowlink value. It's one of the landmark results in graph algorithms.
• 1978 — Sambasiva Rao Kosaraju describes the elegant two-pass method: one DFS on the graph, a second on the transpose. Simpler to prove, and still linear.
• 1990s onward — SCCs become a standard tool in 2-SAT solving, compiler data-flow analysis, and dependency-cycle detection.

Why it mattered then: it turned an O(V · (V + E)) pairwise chore into a single linear pass. That's the same leap KMP made for strings — the moment a "for every pair" question becomes "one clever sweep."

Inside the inventor's headCopy Anchor Link

The brute-force idea is honest and slow. For each vertex u, run a search to see who u reaches, and another search on the reversed graph to see who reaches u. Where the two sets intersect, you have u's component. Do this for every vertex and you're at O(V · (V + E)).

Tarjan's insight is that DFS already discovers the cycles for free. When you hit an edge back to a vertex still on the current DFS path, you've closed a loop. So he tracks two numbers per vertex:

• disc[u] — the order in which u was first visited (a timestamp).
• low[u] — the smallest disc reachable from u's subtree, including via one back edge.

If low[u] comes out equal to disc[u], then nothing in u's subtree can escape backward past u — meaning u is the root of an SCC, and everything discovered after u and still unaccounted for sits above it on a stack.

Contrast the two mindsets:

// Naive: u and v share an SCC iff each can reach the other.// One search per vertex is O(V * (V + E)).function reachable(from, to);         // BFS/DFS — O(V + E) per call// Tarjan: a single DFS emits every SCC in O(V + E) total.function tarjanSCC(n, adj);

Kosaraju later found a different, almost suspiciously simple route: run a DFS, record the order vertices finish, then DFS the transpose graph in reverse finishing order. Each transpose-DFS tree is exactly one SCC. Two passes, same linear time, easier to argue about.

The final approachCopy Anchor Link

Let's make Tarjan's method concrete, then mention Kosaraju's as the alternative.

The walkCopy Anchor Link

The invariantsCopy Anchor Link

1. Discovery order. disc[u] increases with each new vertex visited; it is unique.
2. Lowlink meaning. low[u] is the smallest disc reachable from u's DFS subtree using tree edges plus at most one edge back to a vertex that is still on the stack.
3. The stack is the frontier. It holds exactly the vertices discovered but not yet assigned to an SCC, in DFS order. When low[u] == disc[u], the vertices from the top of the stack down to and including u form one SCC — pop them off.
4. Order of output. Tarjan emits SCCs in reverse topological order of the condensation.

A worked traceCopy Anchor Link

Graph: 0 → 1 → 2 → 0 (a 3-cycle) and 2 → 3 (3 hangs off, no way back). So we expect SCCs {0, 1, 2} and {3}.

Run Tarjan from 0:

Two SCCs, found in one DFS. The condensation {0,1,2} → {3} is a DAG. ✓

It in codeCopy Anchor Link

function tarjanSCC(n, adj) {  const disc = new Array(n).fill(0);  const low = new Array(n).fill(0);  const onStack = new Array(n).fill(false);  const comp = new Array(n).fill(-1);  const stack = [];  let timer = 0, comps = 0;  const dfs = (u) => {    disc[u] = low[u] = ++timer;    stack.push(u);    onStack[u] = true;    for (const v of adj[u]) {      if (disc[v] === 0) {        dfs(v);        low[u] = Math.min(low[u], low[v]);      } else if (onStack[v]) {        low[u] = Math.min(low[u], disc[v]);      }    }    if (low[u] === disc[u]) {                 // u roots an SCC      while (true) {        const w = stack.pop();        onStack[w] = false;        comp[w] = comps;        if (w === u) break;      }      comps++;    }  };  for (let u = 0; u < n; u++) if (disc[u] === 0) dfs(u);  return comp;}

ComplexityCopy Anchor Link

Tarjan uses one DFS and no transpose; Kosaraju needs the reversed graph but reads more like plain DFS. Both are optimal — you can't do better than looking at every edge once.

The other algorithm: KosarajuCopy Anchor Link

Two passes, and the second pass's DFS trees are the SCCs:

function kosaraju(n, adj, radj) {  const seen = new Array(n).fill(false);  const order = [];  const dfs1 = (u) => {                          // pass 1 on G    seen[u] = true;    for (const v of adj[u]) if (!seen[v]) dfs1(v);    order.push(u);                               // push on finish  };  for (let u = 0; u < n; u++) if (!seen[u]) dfs1(u);  const comp = new Array(n).fill(-1);  let c = 0;  const dfs2 = (u) => {                          // pass 2 on G^T    comp[u] = c;    for (const v of radj[u]) if (comp[v] === -1) dfs2(v);  };  for (let i = order.length - 1; i >= 0; i--) {  // reverse finish order    const u = order[i];    if (comp[u] === -1) { dfs2(u); c++; }  }  return comp;}

Condensing to a DAGCopy Anchor Link

Shrinking each SCC to one node, and keeping the edges between components, always yields a DAG — because if two components could reach each other, they'd have been one component. That DAG is called the condensation:

Where you meet it todayCopy Anchor Link

• 2-SAT. Encode each clause (a ∨ b) as two implications, build the graph, run SCCs, and the formula is satisfiable exactly when no variable shares a component with its negation.
• Compilers. A call graph's SCCs are the mutually recursive function groups; detecting them, and analyzing loops (natural loops live inside SCCs), is routine in optimizing compilers.
• Package and build systems. A dependency cycle is a nontrivial SCC — the reason your build fails with "circular dependency" instead of looping forever.
• Web and social graphs. Condensing link graphs surfaces tightly-knit clusters and strongly-connected "cores" of a network.

// A vertex is on a cycle iff its SCC has more than one member.function cyclicVertices(n, adj) {  const comp = tarjanSCC(n, adj);  const size = new Map();  for (const c of comp) size.set(c, (size.get(c) ?? 0) + 1);  const onCycle = [];  for (let u = 0; u < n; u++) {    if (size.get(comp[u]) > 1) onCycle.push(u);  }  return onCycle;}

A lone vertex with a self-loop is also "on a cycle," so in practice you'd OR that in — a one-line detail on top of the same SCC machinery.

RecapCopy Anchor Link

• An SCC is a maximal set of vertices that are all mutually reachable — the cyclic "knots" of a directed graph.
• Tarjan's algorithm finds every SCC in one DFS using discovery times, a lowlink value, and a stack; when low[u] == disc[u], pop a component. O(V + E).
• Kosaraju's method does it in two DFS passes — one on the graph, one on its transpose — with the same linear bound.
• Shrinking every SCC yields the condensation, always a DAG, which is why SCCs drive 2-SAT, cycle analysis, and compiler call-graph reasoning.

Next up: The Archive — you've reached the end of the advanced track. Head back to the index and pick your next thread.