Strongly Connected Components (SCC) - YessineJallouli/Competitive-Programming GitHub Wiki

#include <bits/stdc++.h>
#define ll long long
#define SaveTime ios_base::sync_with_stdio(false), cin.tie(0);

using namespace std;

const int N = 2e5+7;
vector<vector<int>> graph(N);
vector<vector<int>> inv_graph(N);

deque<int> p;
deque<int> component;

bool marked[N];
int cmp[N];

void dfs(int node) {
   if (marked[node])
      return;
   marked[node] = true;
   for (int v : graph[node])
      dfs(v);
   p.push_front(node);
}

void dfs1(int node) {
   if (marked[node])
      return;
   marked[node] = true;
   for (int v : inv_graph[node])
      dfs1(v);
   component.push_front(node);
}

int main() {
   SaveTime
   int n,m; cin >> n >> m;
   for (int i = 0; i < m; ++i) {
      int a,b; cin >> a >> b;
      graph[a].push_back(b);
      inv_graph[b].push_back(a);
   }
   for (int i = 0; i < n; i++)
      dfs(i);
   for (int i = 0; i <= n; i++)
      marked[i] = false;
   int scc = 0;
   for (int i = 0; i < n; i++) {
      if (marked[p[i]])
         continue;
      component.clear();
      dfs1(p[i]);
      for (int j : component)
         cmp[j] = scc;
      scc++;
   }
}