tarjan

#include<iostream>
#include<stack>
#include<vector>
using namespace std;
const int maxn = 1e6+5;

int n, m;
vector<int> edge[maxn];
namespace SCC{
    int cnt, cntb;
    vector<int> belong[maxn];
    bool instack[maxn];
    int dfn[maxn];
    int low[maxn];
    stack<int> s;

    void init(){
        cnt = cntb = 0;
        stack<int> _s;
        swap(_s, s);
        for(int i = 1; i < n; i++){
            edge[i].clear();
            belong[i].clear();
            instack[i] = false;
            dfn[i] = low[i] = 0;
        }    
    }
    void Tarjan(int u){
        dfn[u] = low[u]= ++cnt;
        s.push(u);
        instack[u] = true; 
        for(int i = 0; i < edge[u].size(); i++){
            int v = edge[u][i];
            if(!dfn[v]){
                Tarjan(v);
                low[u] = min(low[u], low[v]);
            }else if(instack[v])    low[u] = min(low[u], dfn[v]);    
        }
        if(dfn[u] == low[u]){
            ++cntb;
            while(233){
                int node=s.top();
                s.pop();
                instack[node] = false;
                belong[cntb].push_back(node);    
                if(node == u)    break;
            }
        }
    }
}

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= m; i++){
        int u, v;
        cin >> u >> v;
        edge[u].push_back(v);
    }
    SCC::Tarjan(1);
    cout << "id  :";
    for(int i = 1; i <= n; i++)
        cout << i << " ";
    cout << endl;

    cout << "dfn :";
    for(int i = 1; i <= n; i++)
        cout << SCC::dfn[i] << " ";
    cout << endl;

    cout << "low :";
    for(int i = 1; i <= n; i++)
        cout << SCC::low[i] << " ";
    cout << endl;

    for(int i = 1; i <= SCC::cntb; i++){
        cout << "SCG " << i << " : ";
        for(int j = 0; j < SCC::belong[i].size(); ++j)
            cout << SCC::belong[i][j] << " ";
        cout << endl;
    }
    return 0;
}