Strongly Connected Components with Tarjan

In an undirected graph, asking "which nodes are connected to each other" is easy. Run a traversal, everything you reach is one component, done.

Directed graphs are meaner. You can reach B from A without any way of getting back. So the useful question becomes: which groups of nodes can all reach each other, in both directions? Those groups are strongly connected components, and inside one, you can start anywhere, wander, and always find a way home.

Why anyone cares

An SCC in a dependency graph is a circular dependency, with every module involved named for you rather than just a yes-or-no answer. An SCC of size 2 or more in a module graph is exactly the thing your bundler warns about.

There is a second use that is worth knowing. Collapse every SCC down to a single node and the graph you are left with is always a DAG, because any cycle would have meant those nodes belonged in the same component. That collapsed graph is called the condensation, and it means you can topologically sort anything, cycles included, as long as you are willing to treat each tangle as one unit.

Two numbers per node

Tarjan runs one DFS and gives every node two numbers as it goes.

Both start out equal. Only lowlink moves, and it only ever goes down, when you discover you can loop back to something older than you thought.

The payoff is one line: when a node finishes and its lowlink still equals its arrival, that node could not reach anything older than itself. It is the oldest node in its component, the point where the whole tangle was entered. Everything sitting above it on the stack belongs to it.

Step through it

This graph has two tangles: A, B, C, D form a loop, and E and F point at each other. Play it and watch the pair above each node. The moment a component closes, its nodes get tinted as a group.

The moment to look for is when D finds its edge back to A. A is still on the stack, so that edge is proof of a loop, and D's lowlink drops to A's arrival number. That drop then propagates back up through C and B as each of them finishes, which is how the whole group ends up agreeing that A is their root.

Also notice E and F close into their own component before A's group does, even though they were reached later. A component closes as soon as its root finishes, not in the order the components were discovered.

Now try the "With a lone node" example, which has three components instead of two. A and B point at each other, C, D and E form a triangle, and F just sits there at the end with a single arrow coming in and nothing going out.

F is still a strongly connected component, all by itself. That catches people out, because F is on no cycle at all. But the definition only asks whether every node in the group can reach every other, and with a group of one that is trivially true: F can reach F by doing nothing. Every node in a directed graph belongs to exactly one SCC, and most real graphs are mostly components of size 1.

F is also the first component to close, before either of the bigger ones, which is worth sitting with for a second. Tarjan finishes F's edges first (there are none), so F's root test passes immediately while C, D, E and A, B are all still open further down the stack.

Why the stack is not just the DFS path

This trips people up. Tarjan keeps its own stack, separate from the DFS call stack, and nodes stay on it after the DFS has backed out of them. They only come off when their component closes.

The stack is answering a specific question: is this node part of a component that is still open? That distinction is what makes the three cases below work out correctly.

That third row is the one people get wrong. If v is already in a closed component, you cannot get back from v to u, so that edge tells you nothing about u's component. Letting it lower u's lowlink would incorrectly glue two separate components together.

In code

function tarjan(nodes, adj) {
  const arrival = new Map();
  const lowlink = new Map();
  const onStack = new Set();
  const stack = [];
  const components = [];
  let counter = 0;

  function strongConnect(u) {
    arrival.set(u, counter);
    lowlink.set(u, counter);
    counter++;
    stack.push(u);
    onStack.add(u);

    for (const v of adj.get(u) ?? []) {
      if (!arrival.has(v)) {
        strongConnect(v);
        // v's component might reach further back than we knew
        lowlink.set(u, Math.min(lowlink.get(u), lowlink.get(v)));
      } else if (onStack.has(v)) {
        // Back edge into a component that is still open.
        // Note: arrival, not lowlink. v is not our ancestor's problem.
        lowlink.set(u, Math.min(lowlink.get(u), arrival.get(v)));
      }
      // else: v is in a closed component, that edge is one-way, skip
    }

    // Could not reach anything older than itself, so u is a root.
    if (lowlink.get(u) === arrival.get(u)) {
      const component = [];
      let w;
      do {
        w = stack.pop();
        onStack.delete(w);
        component.push(w);
      } while (w !== u);
      components.push(component);
    }
  }

  for (const node of nodes) {
    if (!arrival.has(node)) strongConnect(node);
  }
  return components;
}

The whole thing is O(V + E). One DFS, each edge examined once, each node pushed and popped once. That is genuinely impressive for a problem that sounds like it should need repeated searching, and it is why Tarjan is the standard answer rather than the more intuitive approach of running a traversal from every node.

One practical warning, the same one from the DFS lesson: this is recursive, and a long chain will overflow the call stack. The widget above runs an iterative version with an explicit frame stack for exactly that reason.

Check yourself