tarjan算法

求强连通分量：

#include <bits/stdc++.h>

using namespace std;

int main() {
  int n, m;
  scanf("%d%d", &n, &m);

  vector<vector<int>> adj(n + 1);
  for (int i = 0; i < m; i++) {
    int u, v;
    scanf("%d%d", &u, &v);
    adj[u].push_back(v);
  }

  vector<int> dfn(n + 1);  // dfs 森林每个点的时间戳
  vector<int> low(n + 1);  // dfs 森林每个点能跳到的所用点中最小的时间戳
  vector<bool> is_in_stack(n + 1);  // 判断每个点是否在栈中
  vector<int> belong(n + 1);  // 记录每个点属于哪个强连通分量中
  stack<int> stk;  // 存储可能在强连通分量中的点
  int timestamp = 0;  // dfs 时的时间戳
  vector<vector<int>> scc;  // 记录强连通分量
  int cnt = 0;  // 强连通分量的数量

  function <void(int)> dfs = [&](int u) {
    dfn[u] = low[u] = ++timestamp;
    is_in_stack[u] = true;
    stk.push(u);

    for (auto v : adj[u]) {
      if (!dfn[v]) {
        dfs(v);
        low[u] = min(low[u], low[v]);
      } else {
        if (is_in_stack[v]) {
          low[u] = min(low[u], dfn[v]);
        }
      }
    }

    if (dfn[u] == low[u]) {
      ++cnt;
      vector<int> tmp;
      while (true) {
        int v = stk.top();
        tmp.push_back(v);
        belong[v] = cnt;
        is_in_stack[v] = false;
        stk.pop();
        if (v == u) {
          break;
        }
      }
      // 如果需要对强连通分量里的元素排序加此行
      sort(tmp.begin(), tmp.end());
      scc.push_back(std::move(tmp));
    }
  };

  for (int i = 1; i <= n; i++) {
    if (!dfn[i]) {
      dfs(i);
    }
  }
  sort(scc.begin(), scc.end());

  for (auto c : scc) {
    for (auto u : c) {
      printf("%d ", u);
    }
    printf("\n");
  }
}

/*
5 6
1 3
3 1
2 4
4 5
5 2
1 2

ans:
1 3
2 4 5
*/