jsschools

Tarjan's SCC Algorithm

Finds all strongly connected components in a directed graph in a single DFS pass using discovery times and a low-link array to identify SCC roots.

Spec ↗

Syntax

tarjan(graph, V)

Parameters

NameTypeRequiredDescription
graph Map<number, number[]> Yes Directed adjacency list (0-indexed vertices).
V number Yes Number of vertices.

Returns

number[][] — Array of SCCs in reverse topological order of the condensation DAG.

Examples

function tarjan(graph, V) {
  const disc = new Array(V).fill(-1);
  const low  = new Array(V).fill(-1);
  const onStack = new Array(V).fill(false);
  const stack = [];
  const sccs = [];
  let timer = 0;

  function dfs(u) {
    disc[u] = low[u] = timer++;
    stack.push(u);
    onStack[u] = true;

    for (const v of graph.get(u) ?? []) {
      if (disc[v] === -1) { dfs(v); low[u] = Math.min(low[u], low[v]); }
      else if (onStack[v]) low[u] = Math.min(low[u], disc[v]);
    }

    if (low[u] === disc[u]) { // u is an SCC root
      const scc = [];
      let w;
      do { w = stack.pop(); onStack[w] = false; scc.push(w); } while (w !== u);
      sccs.push(scc);
    }
  }

  for (let i = 0; i < V; i++) if (disc[i] === -1) dfs(i);
  return sccs;
}

const g = new Map([[0,[1]],[1,[2]],[2,[0,3]],[3,[4]],[4,[3]]]);
console.log(tarjan(g, 5).map(s => s.sort((a,b)=>a-b)));
Output 
[ [ 3, 4 ], [ 0, 1, 2 ] ]

// Finding bridges (edges whose removal disconnects the graph)
// Uses similar low-link logic on an undirected graph
function bridges(graph, V) {
  const disc = new Array(V).fill(-1), low = new Array(V).fill(-1);
  let timer = 0;
  const result = [];
  const dfs = (u, parent) => {
    disc[u] = low[u] = timer++;
    for (const v of graph.get(u)??[]) {
      if (disc[v]===-1) {
        dfs(v, u);
        low[u] = Math.min(low[u], low[v]);
        if (low[v] > disc[u]) result.push([u, v]);
      } else if (v !== parent) low[u] = Math.min(low[u], disc[v]);
    }
  };
  for(let i=0;i<V;i++) if(disc[i]===-1) dfs(i,-1);
  return result;
}

const g2 = new Map([[0,[1,2]],[1,[0,2]],[2,[0,1,3]],[3,[2]]]);
console.log(bridges(g2, 4)); // edge 2-3 is a bridge
Output 
[ [ 2, 3 ] ]

Notes

| Case | Time | Space | |---------|----------|-------| | Best | O(V + E) | O(V) | | Average | O(V + E) | O(V) | | Worst | O(V + E) | O(V) | Tarjan's algorithm computes SCCs in a single DFS pass, making it more cache-friendly than Kosaraju's two-pass approach. The `low[u]` value represents the smallest discovery time reachable from the subtree rooted at u. The same low-link concept detects **bridges** (cut edges) and **articulation points** (cut vertices) in undirected graphs with minor modifications. SCCs returned are in reverse topological order of the condensation DAG.

See also