SCC

Kosaraju’s Algorithm

Gemini Thread: https://g.co/gemini/share/35c922c32f3f
CP-Algorithms: https://cp-algorithms.com/graph/strongly-connected-components.html

1. Through DFS, find the nodes in post order
2. Now using those order, use the complement graph to find each connected component
   this works since now we would working in the “sink” cycle first and then move on to the rest

void dfs(int u, vector<bool> &visited, vector<vector<int>> &adj,
         vector<int> &order) {
  if (visited[u]) {
    return;
  }
  visited[u] = true;
  for (auto v : adj[u]) {
    dfs(v, visited, adj, order);
  }
  order.push_back(u);
}
 
void dfs2(int u, vector<bool> &visited, vector<vector<int>> &adj,
          vector<int> &order, int t) {
  if (visited[u]) {
    return;
  }
  visited[u] = true;
  order[u] = t;
  for (auto v : adj[u]) {
    dfs2(v, visited, adj, order, t);
  }
}
 
void solve() {
  int n, m;
  cin >> n >> m;
  vector<vector<int>> adj(n);
  vector<vector<int>> adjc(n);
  while (m--) {
    int a, b;
    cin >> a >> b;
    --a;
    --b;
    adj[a].push_back(b);
    adjc[b].push_back(a);
  }
  vector<bool> visited(n, false);
  vector<int> order;
  for (int i = 0; i < n; i++) {
    if (!visited[i]) {
      dfs(i, visited, adj, order);
    }
  }
  reverse(order.begin(), order.end());
  vector<int> belongs(n, 0);
  int cnt = 0;
  fill(visited.begin(), visited.end(), 0);
  for (auto i : order) {
    if (!visited[i]) {
      dfs2(i, visited, adjc, belongs, cnt + 1);
      cnt++;
    }
  }
  cout << cnt << '\n';
  for (auto x : belongs) {
    cout << x << ' ';
  }
}