关于tarjan

RT，这个代码输出的 SCC 缩点后总是一个合法的拓扑序。（参考题目）

bug or feature

vector<int> gv[500001], scc[500001];
stack<int> st;

int dfn[500001], low[500001], ins[500001], cnt = 0, tot = 0, n, m;

inline void add_edge(int u, int v){
    gv[u].push_back(v);
}

void Tarjan(int u){
    dfn[u] = low[u] = ++tot;
    st.push(u); ins[u] = 1;
    for(auto v : gv[u]){
        if(dfn[v] && ins[v])
            low[u] = min(low[u], dfn[v]);
        else if(!dfn[v]){
            Tarjan(v);
            low[u] = min(low[u], low[v]);
        }
    }
    if(low[u] == dfn[u]){
        cnt++; int x = st.top();
        do{
            scc[cnt].push_back(x = st.top());
            ins[st.top()] = 0;
            st.pop();
        }while(x != u);
    }
}

void init_vars(){
    // type your initiating code...
}

void solve(int testcase, ...){
    init_vars();
    cin >> n >> m;
    for(int i = 1; i <= m; i++){
        int u, v; cin >> u >> v;
        u++, v++;
        add_edge(u, v);
    }
    for(int i = 1; i <= n; i++){
        if(!dfn[i]) Tarjan(i);
    }
    cout << cnt << endl;
    for(int i = cnt; i >= 1; i--){
        cout << scc[i].size() << " ";
        for(auto x : scc[i])
            cout << x - 1 << " ";
        cout << endl;
    }
}