强连通分量

constexpr int N = 2e5 + 5;
constexpr int M = 2e5 + 5;

// 原图
int head[N], to[M], nxt[M], tot;
void add(int u, int v) {
    nxt[++tot] = head[u];
    head[u] = tot;
    to[tot] = v;
}

// Tarjan 状态
int dfn[N], low[N], timer;
int scc[N], scc_cnt;
int stk[N], top;



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

    for (int i = head[u]; i; i = nxt[i]) {
        int v = to[i];
        if (!dfn[v]) {
            tarjan(v);
            low[u] = std::min(low[u], low[v]);
        } else if (!scc[v]) {
            low[u] = std::min(low[u], dfn[v]);
        }
    }

    if (dfn[u] == low[u]) {
        ++scc_cnt;
        int v;
        do {
            v = stk[top--];
            scc[v] = scc_cnt;
        } while (v != u);
    }
}


//重建新图 去重边
std::vector<int>g[N];
void rebuild(int n) {
    for(int x=1;x<=n;x++){
        for(int i=head[x];i;i=nxt[i]){
            int y=to[i];
            int u=scc[x],v=scc[y];
            if(u==v)continue;
            g[u].push_back(v);
        }
    }
    for(int i=1;i<=scc_cnt;i++){
        std::sort(g[i].begin(),g[i].end());
        g[i].erase(std::unique(g[i].begin(),g[i].end()),g[i].end());
    }
}

// 规范调用入口
void solve_scc(int n) {
    for (int i = 1; i <= n; ++i) {
        if (!dfn[i]) tarjan(i);
    }
    // rebuild(n);
}