tarjan algorithm for getting strongly connected components for directed graph

tarjan.cpp

/*
Suppose graph is stored in a vector of vector...(g: std::vector<std::vector<int> >)
The graph has n nodes
The components are stored in variable: comp
belong[i] represents component ID for each node, start from 1
*/

int clk, dfu[maxn], low[maxn], sz, belong[maxn];
bool inStack[maxn];
std::stack<int> st;
std::vector<std::vector<int> > comp;
 
void tarjan(int u) {
    dfu[u] = low[u] = ++clk;
    st.push(u);
    inStack[u] = true;
    for (int i = 0; i < g[u].size(); i++) {
        int v = g[u][i];
        if (!dfu[v]) {
            tarjan(v);
            low[u] = std::min(low[u], low[v]);
        } else if (inStack[v]) {
            low[u] = std::min(low[u], dfu[v]);
        }
    }
    if (dfu[u] == low[u]) {
        std::vector<int> v;
        sz++;
        while (true) {
            int hd = st.top();
            st.pop();
            inStack[hd] = false;
            v.pb(hd);
            belong[hd] = sz;
            if (hd == u) break;
        }
        comp.pb(v);
    }
}