Strongly Connected Components with Tarjan

A strongly connected component (SCC) is a part of a directed graph where every node can reach every other node through a path of directed edges. More specifically, it is the largest possible group with this mutual loop. A node can reach all other nodes in the same SCC, and all other nodes in the SCC can reach it.

The obvious method

Before learning about a complex algorithm, it sometimes helps to think about a more direct, less efficient method that works similarly. There is a very simple but slow way to find SCCs, and it is worth looking over before the clever solution.

Pick a node, walk forwards to collect everything it reaches, then walk backwards along reversed edges to collect everything that reaches it. Whatever lands in both sets is mutually reachable with your node, and that set is its component. This algorithm works perfectly fine by the way, just a bit slow.

The map below is a slice of a real flight network. Click any airport to run both walks from it and see where they overlap.

That method is correct, and it costs two traversals per node, so O(V * (V + E)) overall. On a graph with a hundred thousand nodes it is far too slow. Everything below replaces it with a single depth-first search.

The trick

A depth-first search carves a directed graph into a tree, plus leftover edges pointing back at nodes already discovered. Every strongly connected component sits in that tree as one contiguous block: all its nodes in a single subtree, exactly one of them discovered first. Call that one the root.

That follows from the definition. If two nodes can reach each other and DFS enters one, it finds the other before it leaves, so no component is ever split across the tree.

So Tarjan's algorithm basically asks the much simpler question: when DFS finishes a node, is that node a root? If you can answer that, everything discovered since you entered it and not yet claimed is its component.

Two numbers per node

Number each node as you enter it, 0 for the first, 1 for the next. That is its index, fixed once set. Give it a second number, low, answering one question: what is the smallest index I can reach by going down through my subtree and then taking at most one edge back up?

low starts equal to index, since a node reaches itself. It improves twice: returning from a child, take the smaller of your low and the child's low; and on an edge to a node already discovered and still in play, take the smaller of your low and that node's index.

Finish with low below your index and something under you reached an ancestor, so you share a component with it and were not the first into it. Finish with low equal to index and nothing beneath you escaped, which is what being first in a component means. So low equals index marks a root, and everything unclaimed below it is that component.

A full trace

Same map, with Tarjan running on it. Everything the two-traversal method found one airport at a time, this finds in a single pass.

Starting at JFK, neighbors taken in alphabetical order at each stop. Watch the low values climb back up as the recursion unwinds, and each component get outlined the moment its root finishes.

A few things in that trace are worth going back to. JFK visits GRU and LAX before it ever reaches LHR, and both close immediately: each has low equal to its own index, since a leaf with no way back can never be anything but its own component. DXB does the same thing three times over. BKK, SYD, and DXB itself all close as singles, even though DXB is the node every one of those routes leaves from.

Also notice the order components come out: GRU, then LAX, then BKK, then SIN and HND together, then SYD, then DXB on its own, and only at the very end the big loop containing JFK. Tarjan produces components in reverse topological order of the collapsed graph, which is a free bonus. If you need that order the right way round, reverse the output rather than sorting it.

And notice that JFK, the very first node entered, was a root with low 0 equal to its index 0, since the first node of a DFS is always a root of something, because nothing was discovered before it for anything to climb back to.

This has real uses beyond the puzzle. Airlines run exactly this kind of check to find aircraft and crew rotations that return to base without an empty repositioning flight, and to see which parts of a network stay mutually reachable if one hub goes down. The same algorithm, unchanged, finds cycles of mutual dependency in a package manager or clusters of accounts that all follow each other back in a social graph. Anywhere reachability has a direction, Tarjan's algorithm is the fast way to find where it loops back on itself.

The stack

Keep a stack of every node discovered but not yet placed in a finished component. Push on entry. When a root finishes, pop down to and including the root, and those nodes are the component.

The trace above skipped an edge that pointed into an already-finished component, and that is the one part of Tarjan's algorithm that genuinely catches people out. When DFS meets an edge to a node it has already discovered, two different situations need opposite treatment.

One detail the table hides: for a node still on the stack, use its index, not its low. Its low can come from a region that cannot actually reach you, which merges components that should stay apart.

Another example

In the airport problem we briefly discussed the technique of "compressing" a graph's SCCs into one super node to turn a cyclic graph to a DAG for our other algorithms. Here's another practical application of Tarjan's: python import circular dependency detection. In other words, Tarjan's algorithm for detecting cycles in a graph. An edge from one module to another means it imports that module. Python raises ImportError: cannot import name ... (most likely due to a circular import) the moment two modules need each other while either is still mid-import, so the cycle below is the exact shape of the bug, not just an abstract example.

The panel shows each node's index and low as they change. Watch for the moment a low value drops because of a back edge, then watch that value climb the recursion. The components get outlined as they are popped.

PS: Python actually doesn't use Tarjan's for circular dependency detection but frameworks like python's pip and languages like rust or golang do. But the point is they can, its just python uses a memoization caching system.

Big O Complexity

Every node is entered once and pushed once. Every edge is examined once, from its tail. Each node is popped at most once. Add those up and the whole thing is O(V + E), the same as a plain DFS, which is the point of the exercise: it beats the two-traversals-per-node approach by a whole factor of V.

Memory is O(V) for the two number arrays, the stack, and the on-stack flags. The recursion depth can reach V on a long chain, which is the same stack overflow risk any recursive DFS carries, and the same fix applies if you hit it.

Common mistakes

Using low instead of index for an edge to a stacked node. The single most common error, and a nasty one because small graphs often give the right answer anyway. Components come out merged that should be separate.

Updating low from a node that is already off the stack. Same symptom, different cause. A finished component cannot reach you, so an edge into one carries no information about cycles and must be skipped entirely.

Only running the DFS from one node. A directed graph is very often not reachable from any single starting point. Loop over every node and start a fresh DFS from any that is still undiscovered, exactly as with counting connected components.

Expecting components in topological order. They actually come out reversed, very useful if you know it.

Forgetting that a single node is a component. A node on no cycle at all forms a component of size one. In the trace above, schemas and config are each their own component. Code that only records components of two or more will silently drop most of the graph.

The implementation

Short, considering what it does, and the two comment lines are where all the difficulty was.

function tarjan(graph) {
  const index = new Map();      // discovery order
  const low = new Map();        // lowest index reachable, see above
  const onStack = new Set();
  const stack = [];
  const components = [];
  let counter = 0;

  function visit(v) {
    index.set(v, counter);
    low.set(v, counter);
    counter++;
    stack.push(v);
    onStack.add(v);

    for (const w of graph.neighbors(v)) {
      if (!index.has(w)) {
        visit(w);                                   // tree edge
        low.set(v, Math.min(low.get(v), low.get(w)));
      } else if (onStack.has(w)) {
        // w is an ancestor or a sibling still being processed, so it can
        // reach back to v. Use its INDEX, not its low.
        low.set(v, Math.min(low.get(v), index.get(w)));
      }
      // w visited but off the stack: it is in a finished component that
      // cannot reach us. Ignore it entirely.
    }

    if (low.get(v) === index.get(v)) {              // v is a root
      const component = [];
      let w;
      do {
        w = stack.pop();
        onStack.delete(w);
        component.push(w);
      } while (w !== v);
      components.push(component);
    }
  }

  for (const v of graph.nodes) if (!index.has(v)) visit(v);
  return components;
}

Kosaraju's algorithm

Tarjan's algorithm finds every component in a single depth-first search. Kosaraju's algorithm gets the same answer with two passes, trading that extra work for an idea that's easier to hold in your head: run a DFS and record the order nodes finish in, then run a second DFS on the graph with every edge reversed, starting from whichever unvisited node finished last. The node that finishes last always belongs to a source component, one nothing else points into, and reversing every edge turns a source into a sink, so the second search can only wander inside that one component before it runs out of edges to follow. Each tree the second pass grows is exactly one strongly connected component.

function kosaraju(graph) {
  const visited = new Set();
  const finishOrder = [];

  function dfs(v) {
    visited.add(v);
    for (const w of graph.neighbors(v)) {
      if (!visited.has(w)) dfs(w);
    }
    finishOrder.push(v);          // record on the way out, not the way in
  }
  for (const v of graph.nodes) if (!visited.has(v)) dfs(v);

  // Build the transpose: every edge flipped.
  const reverse = new Map(graph.nodes.map((v) => [v, []]));
  for (const v of graph.nodes) {
    for (const w of graph.neighbors(v)) reverse.get(w).push(v);
  }

  visited.clear();
  const components = [];

  function collect(v, component) {
    visited.add(v);
    component.push(v);
    for (const w of reverse.get(v)) {
      if (!visited.has(w)) collect(w, component);
    }
  }

  while (finishOrder.length > 0) {
    const v = finishOrder.pop();    // latest finisher first
    if (!visited.has(v)) {
      const component = [];
      collect(v, component);
      components.push(component);
    }
  }
  return components;
}

Check yourself