各色Tarjan集合

#include<bits/stdc++.h>
using namespace std;
const int N=100000,M=200000;
//所有Tarjan都要：
// dfn[N],low[N],cnt=1,st,scc,zhan[N],top,前向星,vector<int>SCC[N]
//强连通 ,belong[N],inq[N]
//割边，边双 bridge[N], belong[N]
//点双，割点 cut[N],root
int dfn[N],low[N],cnt=1,zhan[N],top,st,belong[N],scc,head[N],root,n;
bool bridge[M],inq[N],cut[N];
vector <int>SCC[N];
struct bian
{
    int nxt,to;
}b[M];
void add(int from,int to)
{
    b[++cnt].nxt=head[from];
    b[cnt].to=to;
    head[from]=cnt;
}
void Tarjan1(int cur)//强连通
{
    dfn[cur]=low[cur]=++st;
    zhan[++top]=cur;inq[cur]=true;
    int i=head[cur],v;
    while(i!=0)
    {
        v=b[i].to;
        if(dfn[v]==0)
        {
            Tarjan1(v);
            low[cur]=min(low[cur],low[v]);
        }
        else
        {
            if(inq[v]==true)
            {
                low[cur]=min(low[cur],dfn[v]);
            }
        }    
        i=b[i].nxt;
    }
    if(low[cur]==dfn[cur])
    {
        scc++;
        int ding;
        do
        {
            ding=zhan[top];
            inq[ding]=false;
            zhan[top--]=0;
            belong[ding]=scc;
            SCC[scc].push_back(ding);
        }while(ding!=cur);
    }
}
void Tarjan2(int cur,int pre)//割边，边双 
{
    dfn[cur]=low[cur]=++st;
    zhan[++top]=cur;
    int i=head[cur],v;
    while(i!=0)
    {
        v=b[i].to;
        if(i!=pre)
        {
            if(dfn[v]==0)
            {
                Tarjan2(v,i^1);
                low[cur]=min(low[cur],low[v]);
                if(low[v]>dfn[cur])
                {
                    bridge[i]=bridge[i^1]=true;
                    scc++;
                    int ding;
                    do
                    {
                        ding=zhan[top];
                        zhan[top--]=0;
                        belong[ding]=scc;
                        SCC[scc].push_back(ding);
                    }while(ding!=v);
                }
            }
            else
                low[cur]=min(low[cur],dfn[v]);
        }
        i=b[i].nxt;
    }
}
void Tarjan3(int cur)
{
    dfn[cur]=low[cur]=++st;
    zhan[++top]=cur;
    int i=head[cur],v,child=0;
    while(i!=0)
    {
        v=b[i].to;
        if(dfn[v]==0)
        {
            child++;
            Tarjan3(v);
            low[cur]=min(low[cur],low[v]);
            if(low[v]>=dfn[cur])
            {
                if(root!=cur)
                    cut[cur]=true;    
                scc++;
                int ding;
                do
                {
                    ding=zhan[top];
                    zhan[top--]=0;
                    SCC[scc].push_back(ding);
                }while(ding!=v);
                SCC[scc].push_back(cur);
            }
        }
        else
            low[cur]=min(low[cur],dfn[v]);
        i=b[i].nxt;
    }
    if(cur==root&&child>=2)
    {
        cut[cur]=true;
    }
}
int main()
{
    for(int i=1;i<=n;i++)
    {
        if(dfn[i]==0)
            Tarjan1(i);
        if(dfn[i]==0)
        {
            Tarjan2(i,0);
            int ding; 
            while(top>0)
            {
                ding=zhan[top];
                zhan[top--]=0;
                SCC[scc].push_back(ding);
            }
        }
        if(dfn[i]==0)
            root=i,Tarjan3(i);
    }
    return 0;
}

特殊点：
强连通的出栈在函数末,进入条件low[cur]=dfn[cur],break条件ding!=cur,注意要维护是否在栈中的数组inq,dfn[v]!=0且inq[v]==true时,才能进入else语句中更新low[cur];

边双和割边出栈在Tarjan过程中的dfn[v]=0中,判断是low[v]>dfn[cur],break条件ding!=v,结束后要清栈;

割点和点双联通在Tarjan过程中的dfn[v]=0中,判断是low[v]>=dfn[cur],break条件ding!=v,注意求割点时,若cur=root且child>=2,为割点;