S

```
// Compute the node priorities, which will be used to determine the order in which we perform transposed DFS.
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)
}
// Nodes that end their DFS earlier are pushed onto the stack first and have lower priority.
stack.push(node)
}
// Return the transpose of graph. The tranpose of a directed graph is a graph where each of the edges are flipped.
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
}
// Computes the SCC that contains the given node
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)
}
}
/**
* @function kosajaru
* @description Given a graph, find the strongly connected components(SCC). A set of nodes form a SCC if there is a path between all pairs of points within that set.
* @Complexity_Analysis
* Time complexity: O(V + E). We perform two DFS twice, and make sure to visit each disconnected graph. Each DFS is O(V + E).
* Space Complexity: O(V + E). This space is required for the transposed graph.
* @param {[number, number][][]} graph - The graph in adjacency list form
* @return {number[][]} - An array of SCCs, where an SCC is an array with the indices of each node within that SCC.
* @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
}
```