Strongly Connected Components

Imagine a city whose streets are all one-way. Some neighbourhoods are tightly connected: you can drive from any intersection to any other and back again by following the one-way signs. Other districts are not — you can reach them but you can never return. Those tightly-connected pockets are strongly connected components (SCCs).

More precisely, given a directed graph, a strongly connected component is a maximal set of vertices such that there is a directed path from every vertex in the set to every other. Two nodes belong to the same SCC if and only if they lie on a common directed cycle.

The question "what are all the SCCs?" might sound like it requires many passes over the graph, one per component. In 1972, Robert Tarjan showed otherwise: a single depth-first search (DFS) is enough — the algorithm runs in $O(V + E)$ time, where V is the number of vertices and E the number of edges. This is solved: the problem is in P, and linear time is optimal because you must at least read the graph.

Tarjan's algorithm works by assigning each node a discovery index and a low-link value (the smallest index reachable via the current DFS tree and one back-edge). It uses a stack to collect candidates, popping an entire SCC the moment it recognises a root — a node whose low-link equals its own index.

Draw a directed graph and let Tarjan's algorithm find its strongly connected components. Click two nodes to add a directed edge between them, then press Find SCCs. Each colour is one component; nodes that form no cycle appear alone.

<p class="hint">{{hint}}</p>
<canvas id="canvas" width="480" height="320"></canvas>
<div class="controls">
  <button id="run" type="button">{{btn_run}}</button>
  <button id="reset" type="button" class="ghost">{{btn_reset}}</button>
  <button id="example" type="button" class="ghost">{{btn_example}}</button>
</div>
<div class="status" id="status">{{status_initial}}</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; margin: 0; color: #222; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .6rem; line-height: 1.45; }
canvas { display: block; border: 1px solid #cdd9e3; border-radius: 10px;
         background: #f7f9fb; cursor: crosshair; max-width: 100%; touch-action: none; }
.controls { display: flex; gap: .5rem; flex-wrap: wrap; margin-top: .6rem; }
button { font: 600 14px system-ui; padding: .42rem .85rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.status { font-size: .95rem; font-weight: 600; margin-top: .5rem; min-height: 1.4em; }
.status.ok  { color: #0a7d33; }
.status.bad { color: #c92f3c; }

// Code not found

Notice how nodes on a directed cycle always land in the same colour. Add a back-edge to link two previously separate groups and they merge into one large SCC. The algorithm never restarts the DFS — it sweeps the whole graph exactly once, using the low-link trick to spot the root of each component on the fly.

How hard is it to decompose a directed graph into its SCCs?

• Lower bound: you must at least read every vertex and edge, so no algorithm can do better than $O(V + E)$.
• Tarjan's algorithm (1972): one DFS with a stack and two integer labels per node. Runs in $O(V + E)$ — optimal. Proven by Robert Tarjan.
• Kosaraju's algorithm (1978): two DFS passes — one on the original graph, one on the transposed graph in reverse finish order. Also $O(V + E)$, a bit simpler to explain.
• Both are in P — in fact in linear time, meaning the problem is as easy as reading the input.

Once you have the SCCs, you can build the condensation graph: collapse each SCC to a single super-node. The condensation is always a directed acyclic graph (DAG), because any cycle between two SCCs would merge them into one. This DAG makes many downstream problems tractable — for example, 2-SAT (deciding a certain class of boolean formulas) reduces to an SCC decomposition plus a topological-sort pass on the condensation, as explored in the 2-SAT vs 3-SAT article.

The contrast with the related problem of finding all Hamiltonian cycles is stark: that problem is NP-complete, yet finding all directed cycles (in the sense of decomposing into SCCs) is linear. The difference is that SCCs care only about existence of a path, not its length or cost.

The SCC decomposition is a fundamental primitive that appears across computer science:

• Compilers and program analysis: finding loops in a control-flow graph is exactly SCC detection. Loop-optimisation passes (unrolling, vectorisation) target strongly connected subgraphs.
• Deadlock detection: in resource-allocation graphs, a deadlock corresponds to a cycle — an SCC with more than one node. Tarjan finds all deadlocks in one scan.
• Web and social graphs: PageRank's iterative computation needs to know which pages can reinforce each other — those are the SCCs of the web graph. Community detection in social networks also leans on mutual reachability.
• Boolean satisfiability: 2-SAT (satisfying a formula where each clause has exactly two literals) is solvable in linear time precisely by building an implication graph and finding its SCCs.
• Circuit simulation: feedback loops in digital circuits are the SCCs; simulators must identify them to handle latches and sequential logic correctly.
• Package dependency resolution: cyclic dependencies in package managers are SCCs; resolvers detect them to report or break cycles.

Almost any time you ask "which parts of this network are mutually dependent?", you are asking for SCCs.

Strongly connected components capture the deepest structure of a directed graph: the islands of mutual reachability where every node can visit every other. Tarjan's 1972 algorithm finds all of them in a single linear-time DFS — a genuinely beautiful result that has aged perfectly.

The condensation DAG it produces turns a tangled directed graph into a clean hierarchy, unlocking efficient solutions to problems from 2-SAT to deadlock detection. Unlike many problems on graphs, this one is fully solved: you cannot do it faster than $O(V + E)$, and Tarjan's algorithm meets that bound exactly.

So whenever you face a directed graph and need to know which nodes truly belong together, remember: one DFS pass, one stack, and Robert Tarjan already worked out the rest in 1972.