无向图tarjan

发布时间 2023-11-29 21:41:47作者: 卡布叻_周深

· 区别于有向图(他的儿子是可能等于他的爸爸的)所以需要这么打

tarjan(1,0);
void tarjan(int x,int fa)
{
    dfn[x]=low[x]=++tot;
    q.push(x),ins[x]=1;
    for(int y:e[x])
        if(y==fa) continue;//他的儿子是可能等于他的爸爸的
        else if(!dfn[y])
            tarjan(y,x),low[x]=min(low[x],low[y]);
        else if(ins[y])
            low[x]=min(low[x],dfn[y]);
    if(dfn[x]==low[x])
    {
        int y;++cnt;
        while(y!=x)
            y=q.top(),
            q.pop(),
            ins[y]=0,
            color[y]=cnt;
    }
}