Graph theory. Strongly Connected Components (SCCs)

On this page

Interactive

Tarjan groups mutually reachable vertices into SCCs

Next SCCAutoReset

Directed graph

Press Next SCC to reveal the first component.

SCCs collapse to a directed acyclic graph

Strongly connected components with Tarjan’s algorithm

In a directed graph, vertices are strongly connected when each can reach the other. A strongly connected component (SCC) is a maximal set with this mutual-reachability property. Collapsing each SCC to one vertex produces a directed acyclic graph, which is useful for analyzing dependencies and reachability.

Tarjan’s one-pass idea

Tarjan’s algorithm finds every SCC in O(V + E) time with one depth-first search (DFS). For each vertex v, index[v] is its discovery number. lowLink[v] is the smallest discovery number reachable from v by following DFS-tree edges and, at most once at the end, an edge to a vertex still on the active stack.

A DFS-tree child propagates its lowLink to its parent after the child finishes. An edge to a vertex still on the stack uses that vertex’s index; an edge to a vertex already removed from the stack is ignored. The active stack is not the same as the recursive call stack: it holds vertices whose SCC has not yet been completed.

When lowLink[v] === index[v], no vertex reachable from v in its DFS subtree can connect back to an earlier active vertex. Thus v is the root of one SCC; pop the active stack through v to collect exactly that component. Starting DFS at each still-unvisited vertex also handles disconnected portions of the graph.

JavaScript implementation

The function accepts an adjacency list graph, where graph[u] lists the 0-based destinations of outgoing edges from u, and returns arrays of 0-based vertices. Assume every listed destination is a valid index. Component order and order within each component are unspecified.

function stronglyConnectedComponents(graph) {
  const n = graph.length;
  const index = Array(n).fill(-1);
  const lowLink = Array(n).fill(0);
  const onStack = Array(n).fill(false);
  const stack = [];
  const components = [];
  let nextIndex = 0;

  function visit(v) {
    index[v] = nextIndex;
    lowLink[v] = nextIndex;
    nextIndex += 1;
    stack.push(v);
    onStack[v] = true;

    for (const w of graph[v]) {
      if (index[w] === -1) {
        visit(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]) {
      const component = [];
      let w;
      do {
        w = stack.pop();
        onStack[w] = false;
        component.push(w);
      } while (w !== v);
      components.push(component);
    }
  }

  for (let v = 0; v < n; v += 1) {
    if (index[v] === -1) visit(v);
  }

  return components;
}

For the graph with edges 0→1, 1→2, 2→0, 2→3, 3→4, 4→3, and 4→5, the result consists of {0,1,2}, {3,4}, and {5} (in any order). The first three vertices form a cycle, vertices 3 and 4 form another, and vertex 5 reaches no vertex that can return to it.

The algorithm uses O(V + E) time and O(V) auxiliary space. This implementation is recursive, so call depth can reach O(V); a very deep graph may exceed the JavaScript runtime’s call-stack limit. Use an iterative DFS implementation when that input size is a concern.

Takeaway: discovery indices order the search, low links reveal the earliest active vertex reachable, and popping at a low-link root completes one SCC.