tarjan系列算法代码小结

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

强联通分量

这里的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]); 
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏HansBug's Lab

算法模板——单个值欧拉函数

输入N,输出phi(N) 这样的单个值欧拉函数程序一般见于部分数论题,以及有时候求逆元且取模的数不是质数的情况(逆元:A/B=A*Bphi(p)-1 (mod ...

35850
来自专栏linux驱动个人学习

高通Audio中ASOC的machine驱动

ASoC被分为Machine、Platform和Codec三大部分,其中的Machine驱动负责Platform和Codec之间的耦合以及部分和设备或板子特定的...

1.4K40
来自专栏瓜大三哥

优化策略之Opt_design

opt_design [-retarget] [-propconst] [-sweep] [-bram_power_opt] [-remap]

32860
来自专栏calmound

ZOJ 3631 Watashi's BG(01dp)

01dp不过由于数组过于大,开不开,学了搜索过了,先记录下 还有一种方法 #include<stdio.h> #include<algorithm> using...

37870
来自专栏落影的专栏

OpenGL ES实践教程(二)摄像头采集数据和渲染

教程 这一篇教程是摄像头采集数据和渲染,包括了三部分内容,渲染部分-OpenGL ES,摄像头采集图像部分-AVFoundation和图像数据创建纹理部分-G...

46950
来自专栏Deep learning进阶路

caffe随记(五)---/build/tools/caffe.bin工具简析

1、怎么用这个命令 在caffe根目录下输入如下命令:  ./build/tools/caffe.bin, 得到如下显示 ? usage:caffe<comm...

63300
来自专栏HansBug's Lab

算法模板——LCA(最近公共祖先)

实现的功能如下——在一个N个点的无环图中,共有N-1条边,M个访问中每次询问两个点的距离 原理——既然N个点,N-1条边,则说明这是一棵树,而且联通。所以以1为...

52240
来自专栏数据库

后GWAS时代的数据整合:RegulomeDB和HaploReg数据库

RegulomeDB和HaploReg数据库提供了将大量基因组学数据与非编码突变整合的思路。 1.背景 GWAS研究产生了大量的SNP,大部分在非编码基因组 这...

357100
来自专栏xingoo, 一个梦想做发明家的程序员

剑指OFFER之变态跳台阶(九度OJ1389)

题目描述: 一只青蛙一次可以跳上1级台阶,也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。 输入: 输入可能包含多个测试样例,对...

19780
来自专栏开发与安全

数据结构:图的存储结构之邻接矩阵

图的邻接矩阵(Adjacency Matrix)存储方式是用两个数组来表示图。一个一维的数组存储图中顶点信息,一个二维数组(称为邻接矩阵)存储图中的边或弧的信息...

70080

扫码关注云+社区

领取腾讯云代金券