Тарьян (SCC одним проходом)

1function tarjanSCC(graph: Map<string, string[]>): string[][] {
2  let index = 0
3  const idx = new Map<string, number>()
4  const low = new Map<string, number>()
5  const onStack = new Set<string>()
6  const stack: string[] = []
7  const sccs: string[][] = []
8 
9  function strongconnect(v: string): void {
10    idx.set(v, index)
11    low.set(v, index)
12    index++
13    stack.push(v)
14    onStack.add(v)
15 
16    for (const w of graph.get(v) ?? []) {
17      if (!idx.has(w)) {
18        strongconnect(w)
19        low.set(v, Math.min(low.get(v)!, low.get(w)!))
20      } else if (onStack.has(w)) {
21        low.set(v, Math.min(low.get(v)!, idx.get(w)!))
22      }
23    }
24 
25    // корень SCC: low == idx
26    if (low.get(v) === idx.get(v)) {
27      const comp: string[] = []
28      let w: string
29      do {
30        w = stack.pop()!
31        onStack.delete(w)
32        comp.push(w)
33      } while (w !== v)
34      sccs.push(comp)
35    }
36  }
37 
38  for (const v of graph.keys()) {
39    if (!idx.has(v)) strongconnect(v)
40  }
41 
42  return sccs
43}