Introduction

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)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.

Try It: Watch Tarjan Run

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">Click two nodes to add a directed edge. Click an existing edge to remove it. Press <b>Find SCCs</b> to run Tarjan's algorithm โ€” each colour is one component.</p>
<canvas id="canvas" width="480" height="320"></canvas>
<div class="controls">
  <button id="run" type="button">Find SCCs</button>
  <button id="reset" type="button" class="ghost">Reset graph</button>
  <button id="example" type="button" class="ghost">Load example</button>
</div>
<div class="status" id="status">Click two nodes to add a directed edge, then Find SCCs.</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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Tarjan's SCC algorithm โ€” interactive directed-graph demo.
// Nodes are fixed circles; click two nodes to toggle an edge.
// "Find SCCs" runs Tarjan and colours each component.

const canvas = document.getElementById('canvas');
const ctx    = canvas.getContext('2d');
const W = canvas.width, H = canvas.height;

// SCC palette: 8 distinct colours
const PALETTE = ['#e63946','#2a9d8f','#e9c46a','#457b9d',
                 '#f4a261','#6d2b8f','#3d9a50','#c0392b'];

// 7 fixed node positions
const NODES = [
  {x:80,  y:80},
  {x:240, y:60},
  {x:400, y:80},
  {x:80,  y:240},
  {x:240, y:200},
  {x:400, y:240},
  {x:240, y:300}
];
const N = NODES.length;
const R = 22; // node radius

// Adjacency: edges[u] = Set of v
let edges = Array.from({length: N}, () => new Set());
// SCC colours for each node (-1 = not computed)
let sccColor = new Array(N).fill(-1);
let sccCount = 0;

// Interaction state: first clicked node for edge creation
let firstClick = -1;

function setStatus(msg, cls='') {
  const el = document.getElementById('status');
  el.textContent = msg;
  el.className = 'status ' + cls;
}

// โ”€โ”€ Drawing โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€
function drawArrow(x1, y1, x2, y2, color) {
  // Shorten line so arrowhead touches the circle boundary
  const dx = x2 - x1, dy = y2 - y1;
  const len = Math.hypot(dx, dy);
  if (len < 1) return;
  const ux = dx / len, uy = dy / len;
  const sx = x1 + ux * R, sy = y1 + uy * R;
  const ex = x2 - ux * (R + 4), ey = y2 - uy * (R + 4);

  ctx.beginPath();
  ctx.moveTo(sx, sy);
  ctx.lineTo(ex, ey);
  ctx.strokeStyle = color;
  ctx.lineWidth = 2;
  ctx.stroke();

  // Arrowhead
  const angle = Math.atan2(ey - sy, ex - sx);
  const hw = 7, hl = 12;
  ctx.beginPath();
  ctx.moveTo(ex, ey);
  ctx.lineTo(ex - hl * Math.cos(angle - 0.4), ey - hl * Math.sin(angle - 0.4));
  ctx.lineTo(ex - hl * Math.cos(angle + 0.4), ey - hl * Math.sin(angle + 0.4));
  ctx.closePath();
  ctx.fillStyle = color;
  ctx.fill();
}

function render() {
  ctx.clearRect(0, 0, W, H);

  // Draw edges
  for (let u = 0; u < N; u++) {
    for (const v of edges[u]) {
      const col = sccColor[u] >= 0 && sccColor[u] === sccColor[v]
        ? PALETTE[sccColor[u] % PALETTE.length] : '#8899aa';
      drawArrow(NODES[u].x, NODES[u].y, NODES[v].x, NODES[v].y, col);
    }
  }

  // Draw nodes
  NODES.forEach((n, i) => {
    const col = sccColor[i] >= 0 ? PALETTE[sccColor[i] % PALETTE.length] : '#1d3557';
    ctx.beginPath();
    ctx.arc(n.x, n.y, R, 0, Math.PI * 2);
    ctx.fillStyle = sccColor[i] >= 0 ? col + '33' : '#e8eef3';
    ctx.fill();
    ctx.strokeStyle = col;
    ctx.lineWidth = i === firstClick ? 3.5 : 2;
    ctx.stroke();

    ctx.fillStyle = col;
    ctx.font = 'bold 14px system-ui';
    ctx.textAlign = 'center';
    ctx.textBaseline = 'middle';
    ctx.fillText(String.fromCharCode(65 + i), n.x, n.y);
  });
}

// โ”€โ”€ Tarjan's SCC โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€
function tarjan() {
  const index  = new Array(N).fill(-1);
  const lowlink= new Array(N).fill(0);
  const onStack= new Array(N).fill(false);
  const stack  = [];
  let idx = 0;
  const comp   = new Array(N).fill(-1);
  let numComp  = 0;

  function strongconnect(v) {
    index[v] = lowlink[v] = idx++;
    stack.push(v);
    onStack[v] = true;

    for (const w of edges[v]) {
      if (index[w] === -1) {
        strongconnect(w);
        lowlink[v] = Math.min(lowlink[v], lowlink[w]);
      } else if (onStack[w]) {
        lowlink[v] = Math.min(lowlink[v], index[w]);
      }
    }

    if (lowlink[v] === index[v]) {
      // Pop an SCC
      let w;
      do {
        w = stack.pop();
        onStack[w] = false;
        comp[w] = numComp;
      } while (w !== v);
      numComp++;
    }
  }

  for (let v = 0; v < N; v++) {
    if (index[v] === -1) strongconnect(v);
  }
  return { comp, numComp };
}

// โ”€โ”€ Interaction โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€
function hitNode(x, y) {
  for (let i = 0; i < N; i++) {
    const dx = NODES[i].x - x, dy = NODES[i].y - y;
    if (dx * dx + dy * dy <= R * R) return i;
  }
  return -1;
}

function scaleXY(evt) {
  const rect = canvas.getBoundingClientRect();
  const scaleX = canvas.width  / rect.width;
  const scaleY = canvas.height / rect.height;
  const src = evt.touches ? evt.touches[0] : evt;
  return [(src.clientX - rect.left) * scaleX,
          (src.clientY - rect.top)  * scaleY];
}

function handleClick(x, y) {
  const hit = hitNode(x, y);
  if (hit < 0) { firstClick = -1; render(); return; }

  if (firstClick < 0) {
    firstClick = hit;
    render();
    setStatus(fmt('Now click a second node to add edge %fromCharCode% โ†’', { fromCharCode: String.fromCharCode(65 + hit) }));
    return;
  }

  const u = firstClick, v = hit;
  firstClick = -1;
  sccColor.fill(-1); // reset colours on graph change
  sccCount = 0;

  if (u === v) { render(); setStatus('Self-loops are allowed but do not create SCCs.'); return; }

  if (edges[u].has(v)) {
    edges[u].delete(v);
    setStatus(fmt('Removed edge %fromCharCode% โ†’ %fromCharCode2%.', { fromCharCode: String.fromCharCode(65+u), fromCharCode2: String.fromCharCode(65+v) }));
  } else {
    edges[u].add(v);
    setStatus(fmt('Added edge %fromCharCode% โ†’ %fromCharCode2%. Press Find SCCs.', { fromCharCode: String.fromCharCode(65+u), fromCharCode2: String.fromCharCode(65+v) }));
  }
  render();
}

canvas.addEventListener('click', e => {
  const [x, y] = scaleXY(e);
  handleClick(x, y);
});
canvas.addEventListener('touchend', e => {
  e.preventDefault();
  const [x, y] = scaleXY(e.changedTouches ? {touches:[e.changedTouches[0]]} : e);
  handleClick(x, y);
}, {passive: false});

document.getElementById('run').addEventListener('click', () => {
  const {comp, numComp} = tarjan();
  sccColor = comp;
  sccCount = numComp;
  render();
  // Summarise
  const groups = Array.from({length: numComp}, () => []);
  comp.forEach((c, i) => groups[c].push(String.fromCharCode(65 + i)));
  const singletons = groups.filter(g => g.length === 1).length;
  const multis = groups.filter(g => g.length > 1);
  let msg = fmt('%numComp% SCC%v% found.', { numComp: numComp, v: numComp > 1 ? 's' : '' });
  if (multis.length) msg += "  " + fmt('Cycles: %map%.', { map: multis.map(g => '{' + g.join(',') + '}').join(', ') });
  setStatus(msg, 'ok');
  console.log('SCCs:', groups.map((g,i)=>'SCC'+i+'='+g.join(',')).join(' | '));
});

document.getElementById('reset').addEventListener('click', () => {
  edges = Array.from({length: N}, () => new Set());
  sccColor.fill(-1); firstClick = -1;
  render();
  setStatus('Graph cleared. Click two nodes to add an edge.');
});

document.getElementById('example').addEventListener('click', () => {
  edges = Array.from({length: N}, () => new Set());
  sccColor.fill(-1); firstClick = -1;
  // Example with 3 SCCs: {A,B,D}, {C,E,F}, {G}
  // Aโ†’B, Bโ†’D, Dโ†’A  (cycle)
  edges[0].add(1); edges[1].add(3); edges[3].add(0);
  // Cโ†’E, Eโ†’F, Fโ†’C  (cycle)
  edges[2].add(4); edges[4].add(5); edges[5].add(2);
  // cross edges
  edges[1].add(2); edges[4].add(6);
  render();
  setStatus('Example loaded. Press Find SCCs to colour the components.');
});

render();
setStatus('Click two nodes to add a directed edge, then Find SCCs.');
Result
Console

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.

The Real Complexity

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)O(V + E).
  • Tarjan's algorithm (1972): one DFS with a stack and two integer labels per node. Runs in O(V+E)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)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.

Where It Matters

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.

Conclusion

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)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.

Share this article

Pick a channel โ€” or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/strongly-connected-components/Content licensed under CC BY-NC 4.0.