Tarjan模板

struct SCC {

    int top = 0, cntscc = 0, dfncnt = 0;
    vector<int> dfn, low, stk, instk;
    vector<int> sccnum, sccid;
    vector<vector<int>> g, scc;

    SCC(int n) {
        dfn.assign(n + 1, 0);
        low.assign(n + 1, 0);
        stk.assign(n + 1, 0);
        sccnum.assign(n + 1, 0);
        sccid.assign(n + 1, 0);
        instk.assign(n + 1, 0);
        g.resize(n + 1);
        scc.resize(n + 1);
    }

    void add(int u, int v) {
        g[u].push_back(v);
    }

    void tarjan(int u) {
        dfn[u] = low[u] = ++dfncnt;
        stk[++top] = u;
        instk[u] = 1;

        for (auto v : g[u]) {
            if (!dfn[v]) {
                tarjan(v);
                low[u] = min(low[u], low[v]);
            } else if (instk[v]) {
                low[u] = min(low[u], low[v]);
            }
        }

        if (dfn[u] == low[u]) {
            cntscc ++;
            int v;
            do {
                v = stk[top --], instk[v] = 0;
                sccid[v] = cntscc;
                scc[cntscc].push_back(v);
                sccnum[cntscc] ++;
            } while (u != v);
        }
    }

};