强连通分量，tarjan

强连通：有向图两个点互相可以到达，则称为强连通，强连通分量指将图分成多个子图，每个子图的点都能相互到达，子图就称为强连通分量；

const int N = 1e5 + 5;
vector<int>e[N];
int dfn[N]//dfs顺序
, low[N]//往前跳能到达的最小数
, dex, bel[N]//表示每一个点在哪一个强连通分量中
, cnt;
bool ins[N];//表示是否在栈中
stack<int>s;
vector<vector<int>>scc;
void tarjan(int u) {
    dfn[u] = low[u] = ++dex;
    ins[u] = true;
    s.emplace(u);
    for (int v : e[u]) {
        if (!dfn[v]) 
            tarjan(v);
        if(ins[v])
            low[u] = min(low[u], low[v]);
    }
    if (dfn[u] == low[u])//已经不能往回了
    {
        vector<int>c;
        ++cnt;//连通分量的组数
        while (true) {
            int v = s.top();
            c.emplace_back(v);
            ins[v] = false;
            bel[v] = cnt;
            s.pop();
            if (v == u)
                break;
        }
        sort(c.begin(), c.end());
        scc.emplace_back(c);
    }
}
int mian() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        e[u].emplace_back(v);
    }
    for (int i = 1; i <= n; ++i) {
        if (!dfn[i]) {
            tarjan(i);
        }
    }
    sort(scc.begin(), scc.end());
    for (auto c : scc) {
        for (int u : c) {
            cout << u << ' ';
        }
        cout << endl;
    }
    return 0;
}