Tarjan(强联通分量)

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using i128=__int128;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using db = double;
using ldb = long double;
#define F first
#define S second
#define debug(x) cerr<<#x<<":"<<x<<"\n";
#define debugv(v) cerr<<#v<<":\n";for(int i=1;i<v.size();i++) cerr<<v[i]<<" ";cout<<"\n";
void solve(){
    int n,m;cin>>n>>m;
    vector<set<int>> a(n+1);
    for(int i=1;i<=m;i++){
        int u,v;cin>>u>>v;
        if(u==v) continue;
        a[u].insert(v);
    }
    vector<int> low(n+1),dfn(n+1),scc(n+1);
    stack<int> st;
    int tot=0,cnt=0;
    auto dfs=[&](auto&& self,int u)->void {
        dfn[u]=low[u]=++tot;
        st.push(u);
        for(auto v:a[u]){
            if(!dfn[v]){
                self(self,v);
                low[u]=min(low[u],low[v]);
            }else if(!scc[v]){
                low[u]=min(low[u],dfn[v]);
            }
        }
        if(low[u]==dfn[u]){
            cnt++;
            while(1){
                int v=st.top();st.pop();
                scc[v]=cnt;
                if(u==v) break;
            }
        }
    };
    for(int i=1;i<=n;i++){
        if(!dfn[i]) dfs(dfs,i);
    }
    cout<<cnt<<"\n";
    vector<set<int>> ans(cnt+1);
    for(int i=1;i<=n;i++){
        ans[scc[i]].insert(i);
    }
    sort(ans.begin()+1,ans.end());
    for(int i=1;i<=cnt;i++){
        for(auto x:ans[i]){
            cout<<x<<" ";
        }
        cout<<"\n";
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr),cout.tie(nullptr);
    int t=1;
    // cin>>t;
    while(t--) solve();
    return 0;
}