const getNodePriorities = (
graph: number[][],
visited: boolean[],
stack: number[],
node: number
) => {
if (visited[node]) {
return
}
visited[node] = true
for (const dest of graph[node]) {
getNodePriorities(graph, visited, stack, dest)
}
stack.push(node)
}
const transpose = (graph: number[][]): number[][] => {
const transposedGraph = Array(graph.length)
for (let i = 0; i < graph.length; ++i) {
transposedGraph[i] = []
}
for (let i = 0; i < graph.length; ++i) {
for (let j = 0; j < graph[i].length; ++j) {
transposedGraph[graph[i][j]].push(i)
}
}
return transposedGraph
}
const gatherScc = (
graph: number[][],
visited: boolean[],
node: number,
scc: number[]
) => {
if (visited[node]) {
return
}
visited[node] = true
scc.push(node)
for (const dest of graph[node]) {
gatherScc(graph, visited, dest, scc)
}
}
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
}