/**
 * @function tarjan
 * @description Given a graph, find the strongly connected components(SCC) in reverse topological order. 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 a DFS of (V + E)
 * Space Complexity: O(V). We hold numerous structures all of which at worst holds O(V) nodes.
 * @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. The order of SCCs in the array are in reverse topological order.
 * @see https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm
 */
export const tarjan = (graph: number[][]): number[][] => {
  if (graph.length === 0) {
    return []
  }

  let index = 0
  // The order in which we discover nodes
  const discovery: number[] = Array(graph.length)
  // For each node, holds the furthest ancestor it can reach
  const low: number[] = Array(graph.length).fill(undefined)
  // Holds the nodes we have visited in a DFS traversal and are considering to group into a SCC
  const stack: number[] = []
  // Holds the elements in the stack.
  const stackContains = Array(graph.length).fill(false)
  const sccs: number[][] = []

  const dfs = (node: number) => {
    discovery[node] = index
    low[node] = index
    ++index
    stack.push(node)
    stackContains[node] = true

    for (const child of graph[node]) {
      if (low[child] === undefined) {
        dfs(child)
        if (low[child] < low[node]) {
          // Child node loops back to this node's ancestor. Update the low node.
          low[node] = low[child]
        }
      } else if (stackContains[child] && low[node] > discovery[child]) {
        // Found a backedge. Update the low for this node if needed.
        low[node] = discovery[child]
      }
    }

    if (discovery[node] == low[node]) {
      // node is the root of a SCC. Gather the SCC's nodes from the stack.
      const scc: number[] = []
      let i
      for (i = stack.length - 1; stack[i] != node; --i) {
        scc.push(stack[i])
        stackContains[stack[i]] = false
        stack.pop()
      }
      scc.push(stack[i])
      stackContains[stack[i]] = false
      stack.pop()
      sccs.push(scc)
    }
  }

  for (let i = 0; i < graph.length; ++i) {
    if (low[i] === undefined) {
      dfs(i)
    }
  }
  return sccs
}