tarjan强联通

struct Tarjan:Graph{//强连通分量缩点
    int low[maxn],dfn[maxn],belong[maxn],stk[maxn],instk[maxn],block[maxn];
    int step,color;
    void tarjan(){
        step=color=0;
        for(int i=0;i<=n;i++) dfn[i]=0;
        for(int i=1;i<=n;i++) if(dfn[i]==0) tarjan(i,0);//多个联通快
    }
    void tarjan(int u,int father=0){//此函数不开放
        low[u]=dfn[u]=++step; stk[++stk[0]]=u;instk[u]=1;
        for(int i=head[u];~i;i=edge[i].nex){
            int v=edge[i].v;
            if(dfn[v]) {
                if(instk[v]) low[u]=min(low[u],dfn[v]);
            }
            else{
                tarjan(v,u);
                low[u]=min(low[u],low[v]);
            }
        }
        if(low[u]==dfn[u]){
            block[color+1]=1;
            while(stk[stk[0]]!=u) {
                belong[stk[stk[0]]]=color+1;
                instk[stk[stk[0]--]]=0;
                block[color+1]++;
            }
            belong[stk[stk[0]]]=++color;
            instk[stk[stk[0]--]]=0;
        }
    }
    void rebuild(Dag&dag){
        set<long long>se;
        dag.ini(color);
        for(int u=1;u<=n;u++){
            int uu=belong[u];
            for(int i=head[u];~i;i=edge[i].nex){
                int v=edge[i].v;
                int vv=belong[v];
                if(uu==vv||se.find(uu*1e6+vv)!=se.end())continue;
                se.insert(uu*1e6+vv);
                dag.add_edge(uu,vv);
            }
            dag.dp[uu][u]=1;
            dag.w[uu]=block[uu];
        }
    }
}graph;