getScc

std::vector<int> getScc(const std::vector<std::vector<int>>& g) {
  int n = int(g.size());
  int timer = 0;
  std::vector<int> vis(n, -1);
  std::vector<int> reach(n);
  std::vector<int> stk;
  std::vector<int> scc_id(n);
  std::vector<bool> done(n);
  int new_id = 0;
  auto dfs = [&](auto&& dfs, int x) -> void {
    stk.push_back(x);
    reach[x] = vis[x] = timer++;
    for (const auto& y : g[x]) {
      if (vis[y] == -1) {
        dfs(dfs, y);
        reach[x] = std::min(reach[x], reach[y]);
      } else if (!done[y]) {
        reach[x] = std::min(reach[x], vis[y]);
      }
    }
    if (reach[x] == vis[x]) {
      while (true) {
        int top = stk.back();
        stk.pop_back();
        scc_id[top] = new_id;
        done[top] = true;
        if (top == x) {
          break;
        }
      }
      new_id += 1;
    }
  };
  for (int i = 0; i < n; ++i) {
    if (vis[i] == -1) {
      dfs(dfs, i);
    }
  }
  for (auto& x : scc_id) {
    x = new_id - 1 - x;
  }
  return scc_id;
}