演算法

1function tarjan(adj: number[][]): number[][] {
2  const n = adj.length;
3  const index: (number | null)[] = new Array(n).fill(null);
4  const low: number[] = new Array(n).fill(0);
5  const onStack: boolean[] = new Array(n).fill(false);
6  const stack: number[] = [];
7  const components: number[][] = [];
8  let counter = 0;
9 
10  function visit(v: number): void {
11    index[v] = low[v] = counter++;
12    stack.push(v);
13    onStack[v] = true;
14    for (const w of adj[v]) {
15      if (index[w] === null) {
16        visit(w);
17        low[v] = Math.min(low[v], low[w]);
18      } else if (onStack[w]) {
19        low[v] = Math.min(low[v], index[w]!);
20      }
21    }
22    if (low[v] === index[v]) {
23      const component: number[] = [];
24      let w: number;
25      do {
26        w = stack.pop()!;
27        onStack[w] = false;
28        component.push(w);
29      } while (w !== v);
30      components.push(component);
31    }
32  }
33 
34  for (let v = 0; v < n; v++) if (index[v] === null) visit(v);
35  return components;
36}