| 1 | // Compute the node priorities, which will be used to determine the order in which we perform transposed DFS. |
| 2 | const getNodePriorities = ( |
| 3 | graph: number[][], |
| 4 | visited: boolean[], |
| 5 | stack: number[], |
| 6 | node: number |
| 7 | ) => { |
| 8 | if (visited[node]) { |
| 9 | return |
| 10 | } |
| 11 | visited[node] = true |
| 12 | |
| 13 | for (const dest of graph[node]) { |
| 14 | getNodePriorities(graph, visited, stack, dest) |
| 15 | } |
| 16 | // Nodes that end their DFS earlier are pushed onto the stack first and have lower priority. |
| 17 | stack.push(node) |
| 18 | } |
| 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[][] => { |