///|
/// Directed graph. SCC enumeration is O(n+m), with an explicit DFS stack.
pub struct SccGraph {
  priv adjacency : Array[Array[Int]]
} derive(Debug)

///|
pub fn SccGraph::new(n : Int) -> SccGraph {
  guard n >= 0 && n <= 100000000 else { panic() }
  { adjacency: Array::makei(n, _ => []), }
}

///|
pub fn SccGraph::add_edge(self : SccGraph, from : Int, to : Int) -> Unit {
  guard 0 <= from &&
    from < self.adjacency.length() &&
    0 <= to &&
    to < self.adjacency.length() else {
    panic()
  }
  self.adjacency[from].push(to)
}

///|
/// Components in topological order, with ascending vertices within each component.
pub fn SccGraph::scc(self : SccGraph) -> Array[Array[Int]] {
  let n = self.adjacency.length()
  let order = Array::make(n, -1)
  let low = Array::make(n, 0)
  let active = Array::make(n, false)
  let cursor = Array::make(n, 0)
  let stack : Array[Int] = []
  let visited : Array[Int] = []
  let ids = Array::make(n, -1)
  let mut timer = 0
  let mut count = 0
  for root = 0; root < n; root = root + 1 {
    if order[root] != -1 {
      continue
    }
    order[root] = timer
    low[root] = timer
    timer += 1
    stack.push(root)
    visited.push(root)
    active[root] = true
    while !stack.is_empty() {
      let v = stack[stack.length() - 1]
      if cursor[v] < self.adjacency[v].length() {
        let to = self.adjacency[v][cursor[v]]
        cursor[v] += 1
        if order[to] == -1 {
          order[to] = timer
          low[to] = timer
          timer += 1
          stack.push(to)
          visited.push(to)
          active[to] = true
        } else if active[to] {
          low[v] = Int::min(low[v], order[to])
        }
      } else {
        ignore(stack.pop())
        if low[v] == order[v] {
          while true {
            let u = visited.pop().unwrap()
            active[u] = false
            ids[u] = count
            if u == v {
              break
            }
          }
          count += 1
        }
        if !stack.is_empty() {
          let parent = stack[stack.length() - 1]
          low[parent] = Int::min(low[parent], low[v])
        }
      }
    }
  }
  let groups : Array[Array[Int]] = Array::makei(count, _ => [])
  for v = 0; v < n; v = v + 1 {
    groups[count - 1 - ids[v]].push(v)
  }
  groups
}