tarjan

tcmts.core.analyze.tarjan · #h3lt3qib · term · runs anywhere

Tarjan's SCC. Components come out dependencies-first.

export function tarjan(n: number, succ: (v: number) => Iterable<number>): number[][] {
  let counter = 0;
  const index = Array.from({ length: n }, () => -1);
  const low = Array.from({ length: n }, () => 0);
  const onStack = Array.from({ length: n }, () => false);
  const stack: number[] = [];
  const out: number[][] = [];
  const strong = (v: number) => {
    index[v] = low[v] = counter++;
    stack.push(v);
    onStack[v] = true;
    for (const w of succ(v)) {
      if (index[w] === -1) {
        strong(w);
        low[v] = Math.min(low[v]!, low[w]!);
      } else if (onStack[w]) low[v] = Math.min(low[v]!, index[w]!);
    }
    if (low[v] === index[v]) {
      const comp: number[] = [];
      let w: number;
      do {
        w = stack.pop()!;
        onStack[w] = false;
        comp.push(w);
      } while (w !== v);
      out.push(comp.sort((a, b) => a - b));
    }
  };
  for (let v = 0; v < n; v++) if (index[v] === -1) strong(v);
  return out;
}

tarjan

used by