You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
// Compute the node priorities, which will be used to determine the order in which we perform transposed DFS.
constgetNodePriorities=(
graph: number[][],
visited: boolean[],
stack: number[],
node: number
)=>{
if(visited[node]){
return
}
visited[node]=true
for(constdestofgraph[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.
consttranspose=(graph: number[][]): number[][]=>{
consttransposedGraph=Array(graph.length)
for(leti=0;i<graph.length;++i){
transposedGraph[i]=[]
}
for(leti=0;i<graph.length;++i){
for(letj=0;j<graph[i].length;++j){
transposedGraph[graph[i][j]].push(i)
}
}
returntransposedGraph
}
// Computes the SCC that contains the given node
constgatherScc=(
graph: number[][],
visited: boolean[],
node: number,
scc: number[]
)=>{
if(visited[node]){
return
}
visited[node]=true
scc.push(node)
for(constdestofgraph[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.
