tarjan

强连通

void tarjan(int u){
    vis[u]=true;
    Q.push(u);
    LOW[u]=DFN[u]=++cnt;
    for(int v:g[u]){
        if(!DFN[v]){
            LOW[u]=min(LOW[u],LOW[v]);
        }else if(vis[v])LOW[u]=min(LOW[u],DFN[v]); //还在栈中
    }
    if(DFN[u]==LOW[u]){
        ans++;
        int x;
        do{
            x=Q.top();Q.pop();
            vis[x]=0;num[x]=ans;
        }while(u!=x);
    }
}

割点

void tarjan(int u,int fa){
    int son=0;
    LOW[u]=DFN[u]=cnt++;
    for(int v:g[u]){
        if(!DFN[v]){
            tarjan(v,u);
            son++;
            LOW[u]=min(LOW[u],LOW[v]);
            if(u==root&&son>1||(u!=root&&LOW[v]>=DFN[u]))ge[u]++;
        }
        else if(v^fa)LOW[u]=min(LOW[u],DFN[v]);
    }
}

割边

void tarjan(int u,int fa){
    LOW[u]=DFN[u]=++cnt;
    for(int v:g[u]){
        if(!DFN[v]){
            tarjan(v,u);
            LOW[u]=min(LOW[u],LOW[v]);
            if(LOW[v]>DFN[u]){
                bri.push_back({u,v});
            }
        }
        else if(v^fa)
        LOW[u]=min(LOW[u],DFN[v]);
    }
}

void tarjan(int u,int fa){
    DFN[u] = LOW[u] = cnt++;
    int son = 0;
    for(auto &v:g[u]){
        edge e = edge(u, v);
        if(!DFN[v]){
            Q.push(e);
            tarjan(v, u);
            LOW[u] = min(LOW[u], LOW[v]);
            son++;
            if(LOW[v]>=DFN[u]){
                iscut[u] = true;//u是割点标记一下
                bcc_cut++;
                cut[bcc_cut].clear();
                while(true){
                    edge x = Q.top();
                    Q.pop();
                    if(vis_cut[x.u]!=bcc_cut){
                        cut[bcc_cut].push_back(x.u);
                        vis_cut[x.u] = bcc_cut;
                    }
                    if (vis_cut[x.v] != bcc_cut){
                        cut[bcc_cut].push_back(x.v);
                        vis_cut[x.v] = bcc_cut;
                    }
                    if(x.u^u and x.v^v)break;
                }
            }
        }else if(v^fa&&DFN[v]<DFN[u]){
            Q.push(e);
            LOW[u] = min(LOW[u], DFN[v]);
        }
    }
    if(fa<0&&son==1)iscut[u]=false;
}