graph - Strongly Connected Components

/*
 * Tarjan's Algorithm to find SCC of a directed Graph
 * Complexity: O(V+E)
 *
 * Usage:
 * - init(n) : n is #nodes, 0 indexed
 * - add(u,v): Adds a directed edge from u to v
 * - doscc() : Processes the graph and finds out SCC of the graph
 */

struct scc {
  vector<vector<int>> g;
  vector<int> scc, low, ind;
  int n, T, col;
  void init(int _n) {
    n = _n, T = 0, col = 0;
    g.clear();
    g.resize(n);
    scc.assign(n, -1);
    low.assign(n, -1);
    ind.assign(n, -1);
  }

  void add(int u, int v) { g[u].push_back(v); }

  vector<int> stk;
  void dfs(int u) {
    low[u] = ind[u] = ++T;
    stk.push_back(u);

    for (auto v : g[u]) {
      if (ind[v] == -1)
        dfs(v);
      if (scc[v] == -1)
        low[u] = min(low[u], low[v]);
    }

    if (ind[u] == low[u]) {
      int t;
      do {
        t = stk.back();
        stk.pop_back();
        scc[t] = col;
      } while (t != u);
      col++;
    }
  }
  void doscc() {
    for (int i = 0; i < n; i++)
      if (ind[i] == -1)
        dfs(i);
  }
};