| 19 | |
| 20 | // Return the transpose of graph. The tranpose of a directed graph is a graph where each of the edges are flipped. |
| 21 | const transpose = (graph: number[][]): number[][] => { |
| 22 | const transposedGraph = Array(graph.length) |
| 23 | for (let i = 0; i < graph.length; ++i) { |
| 24 | transposedGraph[i] = [] |
| 25 | } |
| 26 | |
| 27 | for (let i = 0; i < graph.length; ++i) { |
| 28 | for (let j = 0; j < graph[i].length; ++j) { |
| 29 | transposedGraph[graph[i][j]].push(i) |
| 30 | } |
| 31 | } |
| 32 | |
| 33 | return transposedGraph |
| 34 | } |
| 35 | |
| 36 | // Computes the SCC that contains the given node |
| 37 | const gatherScc = ( |