Tarjans Strongly Connected Components (SCC)

tarjans.cpp

template <int MAXN> struct SCC {
    int num[MAXN], low[MAXN];
    bool curProcess[MAXN];
    stack<int> curVis;
    int dfsCnt = 0;
    SCC() { fill(begin(num), end(num), -1), fill(begin(low), end(low), -1); }
    void dfs(int cur) {
        num[cur] = low[cur] = dfsCnt++;
        curProcess[cur] = true;
        curVis.push(cur);
        for (auto v : adj[cur]) {
            if (num[v] == -1)
                dfs(v);
            if (curProcess[v])
                low[cur] = min(low[cur], low[v]);
        }
        if (num[cur] == low[cur]) {
            while (curVis.top() != cur) {
                int t = curVis.top();
                curVis.pop();
                low[t] = low[cur];
                curProcess[t] = false;
            }
            curVis.pop();
            curProcess[cur] = false;
        }
    }
    void tarjans() {
        for (int i = 0; i < N; i++)
            if (num[i] == -1)
                dfs(i);
    }
};