培训补坑(day2：割点与桥+强联通分量)

补坑ing...

好吧，这是第二天。

这一天我们主要围绕的就是一个人：tarjan。。。。。。创造的强联通分量算法

对于这一天的内容我不按照顺序来讲，我们先讲一讲强联通分量，然后再讲割点与桥会便于理解

首先是强联通分量。。

所谓强联通分量即在一个集合中，所有的点都能互通，那么我们就称这一整个集合是一个强联通分量

那么我们怎么求一张图中有几个强联通分量呢？

首先我们要了解tarjan算法中最重要的2个数组（dfn数组：表示该点第一次出现在DFS序列中的时刻;low数组：表示该点所能追溯到的编号最小的节点（或者称为一个点能够到达的编号最小的节点，并且这2个节点互通（在有向图中）））

不废话，上图：

首先我们从任意一点开始dfs，直到走到底（出度为0）

如图我们发现6的出度为0，此时它的low数组与dfn数组相同，我们将他出队，并把它本身标记为一个强联通分量。

我们回到5，发现5和6的情况一样，自己就是一个强联通分量，然后5出队

然后我们继续从3号节点往下搜，发现搜到4号节点，4号节点又追溯到1号节点，发现一号节点已经访问过了,我们更新4的low数组，并将low数组回传。

然后我们从1号节点接着搜，搜到2号节点，2号节点又搜到了4号节点，而且4号节点又访问过了，所以我们认为1 2 3 4这是一个强联通分量，我们把所有low值为1的点都出队，发现队伍都空了，tarjan算法结束。

下面附上tarjan求强联通分量的代码

#include<cstdio>

inline int read()

{

    int x=;char c;

    while((c=getchar())<''||c>'');

    for(;c>=''&&c<='';c=getchar())x=x*+c-'';

    return x;

}

#define MN 10000

#define MM 50000

struct edge{int nx,t;}e[MM+];

int h[MN+],en,d[MN+],l[MN+],cnt,z[MN+],zn,inz[MN+],K;

inline void ins(int x,int y){e[++en]=(edge){h[x],y};h[x]=en;}

void tj(int x)

{

    d[x]=l[x]=++cnt;inz[z[zn++]=x]=;

    for(int i=h[x];i;i=e[i].nx)

    {

        if(!d[e[i].t])tj(e[i].t);

        if(inz[e[i].t]&&l[e[i].t]<l[x])l[x]=l[e[i].t];

    }

    if(d[x]==l[x])for(++K;z[zn]!=x;)inz[z[--zn]]=;

}

int main()

{

    int n,m,i;

    n=read();m=read();

    while(m--)i=read(),ins(i,read());

    for(i=;i<=n;++i)if(!d[i])tj(i);

    printf("%d",K);

}

不过提醒一下：本算法的退队是有问题的，如果出现多组数据需要将stack数组清0，或者在退队过程中把stack清0，具体原因如下：

假如我们上一次昨晚后的stack数组是这样的：

然后我们下一次继续做的时候，假如我们找到一个强联通分量，为1 2 3 4，进行退队操作：

（画图丑，不要介意）

那么我们会发现根本就不能退队，因为本来我们认为是空的地方的low和第一个点的low数组是一样的！所以就会出错！

————————————————我是分割线————————————————

那么我们已经讲完了强联通分量，回头来看看割点与桥：

我们先简单了解一下割点与桥的定义：

割点：假如这个点不存在整个有向图会变成2半

桥:假如不存在这条边，整个有向图会变成2半。

我们再把上面那张图搬出来：

在这张图中，割点有这几个：5，3，但是没有桥（尴尬了）

我们先看看割点的性质，显然割点后面的点的low数组都比割点的low数组大！对！就是这个性质！但是是不是除此之外就没有割点了呢？不是！在下一张图中我们会发现有满足这个性质但同样是割点的点。

所以我们只需要在tarjan算法的同时，在dfs中添加判断即可，但是注意，不要在整个dfs结束之后再来判断，因为我们有可能回溯到low数组比当前点小的点，不过我们不用考虑这些点，只要考虑之后的点就好了。

然后我们来看看下面这张图

这张图中红色的边就是一条桥，那么我们是否又发现了什么性质呢？是的，桥的终点的dfn数组等于low数组。因为如果5能够回溯到4以前的节点那么它就不是一条桥了。

来补一下割点的坑，在下一张图中，此时我们会发现，根节点也是一个割点，但是它并不满足上述割点的性质，所以，割点还有一个判断条件就是它是dfs树的根节点而且它有两棵以上的子树。

下面附上割点与桥的代码QAQ

#include<cstdio>

#define MN 500005

#define min(a,b) ((a)<(b)?(a):(b))

using namespace std;

int x,y,n,m,num=,tot=,dfsn;

int head[MN],low[MN],dfn[MN];

bool gedian[MN];

bool qiao[MN];

struct edge{

    int to,next;

}g[MN*];

void ins(int u,int v){g[++num].next=head[u];head[u]=num;g[num].to=v;}

void tarjan(int u,int fa){

    low[u]=dfn[u]=++dfsn;

    int tmp=;

    for(int i=head[u];i;i=g[i].next)

        if(g[i].to!=fa)

            if(!dfn[g[i].to]){

                tarjan(g[i].to,u);

                low[u]=min(low[u],low[g[i].to]);

                tmp++;

                if (low[g[i].to]>=dfn[u]) gedian[u]=true;

                if(low[g[i].to]==dfn[g[i].to])qiao[i>>]=true;

            }

            else low[u]=min(low[u],dfn[g[i].to]);

    if(fa==-&&tmp<=)gedian[u]=false;

}

int main(){

    scanf("%d%d",&n,&m);

    for(int i=;i<=m;i++)scanf("%d%d",&x,&y),ins(x,y),ins(y,x);

    for(int i=;i<=n;i++)

    if(!dfn[i])tarjan(i,-);

    for(int i=;i<=n;i++)if(gedian[i])printf("%d ",i);

    printf("\n");

    for(int i=;i<=m;i++)if(qiao[i])printf("%d ",i);

    printf("\n");

}

巴特西

培训补坑(day2：割点与桥+强联通分量)

最新文章

热门文章