tarjan系列算法代码小结

attack

发布于 2018-04-10 17:35:47

7100

发布于 2018-04-10 17:35:47

文章被收录于专栏：数据结构与算法数据结构与算法

个人使用，可能不是很详细

强联通分量

这里的dfn可以写成low

因为都是在栈中，只要保证该节点的low值不为本身即可

void tarjan(int now)
{
    dfn[now]=low[now]=++tot;
    s.push(now);
    vis[now]=1;
    for(int i=headE[now];i!=-1;i=E[i].nxt)
    {
        if(!dfn[E[i].v]) 
            tarjan(E[i].v),low[now]=min(low[now],low[E[i].v]);
        else if(vis[E[i].v]) 
            low[now]=min(low[now],dfn[E[i].v]);
    }
    if(low[now]==dfn[now])
    {
        int h;
        colornum++;
        do
        {
            h=s.top();
            color[h]=colornum;
            sum[colornum]+=money[h];
            vis[h]=0;
            s.pop();
            
        }while(h!=now);
    }
}

点双联通分量

条件low[j]>=dfn[i]

栈的边界条件需要特殊判断

void tarjan(int now,int fa)
{
    dfn[now]=low[now]=++tot;
    s.push(now);
    for(int i=head[now];i!=-1;i=edge[i].nxt)
    {
        if(!dfn[edge[i].v]&&edge[i].v!=fa)
        {
            tarjan(edge[i].v,now);
            low[now]=min(low[now],low[edge[i].v]);
            if(low[edge[i].v]>=dfn[now])
            {
                memset(in,0,sizeof(in));//哪些在双联通分量里
                memset(color,0,sizeof(color));
                int h=0,cnt=0;
                do
                {
                    h=s.top();s.pop();
                    in[h]=1;
                    point[++cnt]=h;
                }while(h!=edge[i].v);//warning 
                if(cnt<=1) continue;//必须构成环 
                in[now]=1;point[++cnt]=now;
                if(MakeColor(now,1)==0)
                    for(int j=1;j<=cnt;j++)
                        ans[point[j]]=1;
            }
        }
        if(edge[i].v!=fa) low[now]=min(low[now],dfn[edge[i].v]);
    }
}

边双联通分量

记录一下父亲节点就好

void tarjan(int now,int fa)
{
    dfn[now]=low[now]=++tot;
    s.push(now);
    vis[now]=1;
    for(int i=head[now];i!=-1;i=edge[i].nxt)
    {
        if(!dfn[edge[i].v]&&edge[i].v!=fa) 
            tarjan(edge[i].v,now),low[now]=min(low[now],low[edge[i].v]);
        if(vis[edge[i].v]&&edge[i].v!=fa) low[now]=min(low[now],dfn[edge[i].v]);
    }
    if(dfn[now]==low[now])
    {
        int h=0;
        colornum++;
        do
        {
            h=s.top();
            color[h]=colornum;
            s.pop();
        }while(h!=now);
    }
}

割顶

条件low[j]>=dfn[i]

int tarjan(int now,int fa)
{
    int ch=0;
    dfn[now]=low[now]=++tot;
    for(int i=head[now];i!=-1;i=edge[i].nxt)
    {
        if(!dfn[edge[i].v])
        {
            tarjan(edge[i].v,fa);
            low[now]=min(low[now],low[edge[i].v]);
            if(low[edge[i].v]>=dfn[now]&&now!=fa) cut[now]=1;
            if(now==fa) ch++; 
        }
        low[now]=min(low[now],dfn[edge[i].v]);
    }
    if(now==fa&&ch>=2) cut[now]=1;
}

割边

条件low[v]>dfn[now]

void tarjan(int now,int fa)
{
    dfn[now]=low[now]=++tot;
    for(int i=head[now];i!=-1;i=edge[i].nxt)
    {
        if(!dfn[edge[i].v]) 
        {
            deep[edge[i].v]=deep[now]+1;
            f[edge[i].v]=now;
            tarjan(edge[i].v,now);
            low[now]=min(low[now],low[edge[i].v]);
            if(low[edge[i].v]>dfn[now])
            {
                bridge[edge[i].v]=1;
                ans++;
            }
        }   
        else if(edge[i].v!=fa) low[now]=min(low[now],dfn[edge[i].v]); 
    }
}

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2018-02-27 ，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法