🧠 Mental Model
A strongly connected component (SCC) of a directed graph is a maximal set of vertices
where every vertex can reach every other. Tarjan's finds all SCCs in a single DFS
using two numbers per vertex: its discovery index and its low-link
(the smallest index reachable from its subtree, including via one back-edge).
The insight: a vertex is the "root" of an SCC exactly when it can't reach anything discovered earlier
than itself (low[u] == disc[u]). A stack of "still-open" vertices lets you pop off a
whole SCC when its root finishes.
⚙️ Mechanics
- DFS, assigning each vertex an increasing disc index; init low = disc.
- Push each vertex onto a stack and mark it "on stack."
- For a tree-edge to v: recurse, then low[u] = min(low[u], low[v]).
- For an edge to an on-stack v (back/cross within SCC): low[u] = min(low[u], disc[v]).
- If low[u] == disc[u], pop the stack down to u — that's one SCC.
Low-link invariant: low[u] = the smallest discovery index reachable
from u's DFS subtree using tree edges plus at most one edge to an on-stack vertex.
📐 Correctness
Theorem
low[u] == disc[u] iff u is the root (first-discovered vertex) of
its SCC. Popping the stack down to u yields exactly that SCC.
Proof sketch
If u can reach a vertex w discovered earlier and still on the
stack, then w and u are mutually reachable (u→w by assumption;
w→u because w is an ancestor still open), so they share an SCC and
low[u] < disc[u] — u is not the root. Conversely, if
low[u] = disc[u], nothing in u's subtree escapes to an earlier
open vertex, so u is the earliest member of its SCC. All vertices pushed after
u and still on the stack are precisely the rest of that SCC — they were reachable
from u and could reach back to it. ∎
⚖️ Tarjan vs Kosaraju
| Tarjan | Kosaraju |
|---|
| DFS passes | One | Two (+ graph transpose) |
| Extra structure | Stack + low-link | Finish-order stack + reversed graph |
| Time | O(V + E) | O(V + E) |
| Ease to derive | Trickier (low-link) | Conceptually simpler |
Interview tip: know Tarjan for its single pass and its shared machinery with bridges/articulation points (Day 18). Mention Kosaraju as the simpler-to-explain alternative.
💻 Reference Implementation (Java)
import java.util.*;
private int[] disc, low;
private boolean[] onStack;
private Deque<Integer> stack;
private int timer;
private List<List<Integer>> sccs;
public List<List<Integer>> tarjan(int n, List<Integer>[] adj) {
disc = new int[n]; low = new int[n];
Arrays.fill(disc, -1);
onStack = new boolean[n];
stack = new ArrayDeque<>();
sccs = new ArrayList<>();
timer = 0;
for (int u = 0; u < n; u++) if (disc[u] == -1) dfs(u, adj);
return sccs;
}
private void dfs(int u, List<Integer>[] adj) {
disc[u] = low[u] = timer++;
stack.push(u); onStack[u] = true;
for (int v : adj[u]) {
if (disc[v] == -1) { // tree edge
dfs(v, adj);
low[u] = Math.min(low[u], low[v]);
} else if (onStack[v]) { // back/cross to open vertex
low[u] = Math.min(low[u], disc[v]);
}
}
if (low[u] == disc[u]) { // u is an SCC root
List<Integer> comp = new ArrayList<>();
while (true) {
int w = stack.pop(); onStack[w] = false;
comp.add(w);
if (w == u) break;
}
sccs.add(comp);
}
}
🎭 Problem Variances — SCC in disguise
The tell is directed mutual reachability, cycles that must be collapsed, or
"condense the graph."
| Disguise / phrasing | What's really asked | Twist to handle |
|---|
| "Groups where everyone reaches everyone" (directed) | SCCs directly | Tarjan or Kosaraju |
| "Condense cycles / build the DAG of components" | Condensation graph | Contract each SCC to a node; edges between SCCs form a DAG |
| "2-SAT satisfiable?" | SCC on implication graph | x and ¬x in same SCC ⇒ unsatisfiable |
| "Min edges to make whole graph strongly connected" | Condense, count sources/sinks | Answer = max(sources, sinks) on the condensation |
| "Which nodes can reach a cycle / are in a loop" | SCC size > 1 (or self-loop) | Non-trivial SCCs |
| "Critical dependencies in a directed system" | Component structure | SCC + condensation reasoning |
Recognition heuristic: directed graph + "mutually reachable" or "collapse cycles" = SCC. 2-SAT is the classic disguised application.
⚠️ Common Pitfalls
Using low[v] vs disc[v] wrongly: tree edges update with low[v]; edges to on-stack vertices update with disc[v]. Mixing them breaks SCCs.
Updating low from a finished (off-stack) vertex: ignore cross-edges to popped vertices — only on-stack ones count.
Recursion depth: large graphs may need an explicit stack version.
🎯 Problems
LC 1192
Critical Connections in a Network
Bridges via low-link (Day 18 extends this); same DFS machinery.
Hard
—
2-SAT / implication graph (implement Kosaraju too)
Build implication graph, SCC it; x ∧ ¬x in one SCC ⇒ UNSAT. Great practice.
Hard
📚 References
- Tarjan, R. E. (1972) — "Depth-first search and linear graph algorithms," SIAM J. Comput. 1(2), 146–160. The SCC + low-link paper.
- CLRS, 3rd ed., §22.5 — Strongly connected components (presents Kosaraju's two-pass method).
- Sharir (1981) / Kosaraju (unpublished, 1978) — the transpose-based SCC algorithm.
- Aspvall, Plass & Tarjan (1979) — linear-time 2-SAT via SCCs.