Function kosajaru

graph/kosajaru.ts:64–84

(graph: number[][])

 * @see https://en.wikipedia.org/wiki/Kosaraju%27s_algorithm
 */
export const kosajaru = (graph: number[][]): number[][] => {
  const visited = Array(graph.length).fill(false)

  const stack: number[] = []
  for (let i = 0; i < graph.length; ++i) {
    getNodePriorities(graph, visited, stack, i)
  }

  const transposedGraph = transpose(graph)

  const sccs = []
  visited.fill(false)
  for (let i = stack.length - 1; i >= 0; --i) {
    if (!visited[stack[i]]) {
      const scc: number[] = []
      gatherScc(transposedGraph, visited, stack[i], scc)
      sccs.push(scc)
    }
  }
  return sccs
}