scc.cpp

struct SCC {
  int V, group_cnt;
  vector<vector<int>> adj, radj;
  vector<int> group_num, vis;
  stack<int> stk;

  // V = number of vertices
  SCC(int V)
      : V(V), group_cnt(0), group_num(V), vis(V), adj(V),
        radj(V) {}

  // Call this to add an edge (0-based)
  void add_edge(int v1, int v2) {
    adj[v1].push_back(v2);
    radj[v2].push_back(v1);
  }

  void fill_forward(int x) {
    vis[x] = true;
    for (int i = 0; i < adj[x].size(); i++) {
      if (!vis[adj[x][i]]) {
        fill_forward(adj[x][i]);
      }
    }
    stk.push(x);
  }

  void fill_backward(int x) {
    vis[x] = false;
    group_num[x] = group_cnt;
    for (int i = 0; i < radj[x].size(); i++) {
      if (vis[radj[x][i]]) {
        fill_backward(radj[x][i]);
      }
    }
  }

  // Returns number of strongly connected components.
  // After this is called, group_num contains component
  // assignments (0-based)
  int get_scc() {
    for (int i = 0; i < V; i++) {
      if (!vis[i])
        fill_forward(i);
    }
    group_cnt = 0;
    while (!stk.empty()) {
      if (vis[stk.top()]) {
        fill_backward(stk.top());
        group_cnt++;
      }
      stk.pop();
    }
    return group_cnt;
  }
};