Компоненты сильной связности

1function kosaraju(graph: Map<string, string[]>): string[][] {
2  // 1. порядок выхода DFS на исходном графе
3  const visited = new Set<string>()
4  const order: string[] = []
5  for (const v of graph.keys()) {
6    if (!visited.has(v)) dfs1(v)
7  }
8  function dfs1(v: string): void {
9    visited.add(v)
10    for (const next of graph.get(v) ?? []) {
11      if (!visited.has(next)) dfs1(next)
12    }
13    order.push(v) // вышли — записали
14  }
15 
16  // 2. DFS на перевёрнутом графе в порядке убывания exit-времени
17  const reversed = reverseGraph(graph)
18  const seen = new Set<string>()
19  const sccs: string[][] = []
20  for (const v of [...order].reverse()) {
21    if (seen.has(v)) continue
22    const comp: string[] = []
23    dfs2(v)
24    sccs.push(comp)
25    function dfs2(v: string): void {
26      seen.add(v)
27      comp.push(v)
28      for (const next of reversed.get(v) ?? []) {
29        if (!seen.has(next)) dfs2(next)
30      }
31    }
32  }
33 
34  return sccs
35}