前言

“tarjan陪伴强联通分量

生成树完成后思路才闪光

欧拉跑过的七桥古塘

让你 心驰神往”

----《膜你抄》


正文

稍微了解了一下这个算法的知识,个人认为在理解难度上,求强连通分量<求割边=求割点,所以我们就按照这样的顺序进行 Tarjan 算法的初探吧。


一、求强连通分量

1.什么是强联通分量?

引用度娘的一句话:

有向图强连通分量:在有向图 $G$ 中,如果两个顶点 $v_i,v_j$ 间($v_i>v_j$)有一条从 $v_i$ 到 $v_j$ 的有向路径,同时还有一条从 $v_j$ 到 $v_i$ 的有向路径,则称两个顶点强连通(strongly connected)。如果有向图 $G$ 的每两个顶点都强连通,称 $G$ 是一个强连通图。有向图的极大强连通子图,称为强连通分量(strongly connected components)。

看上去可能有点绕,所以来为大家梳理一下重点。

首先,强连通分量是针对有向图而言的。

其次,对于一个连通分量,其中对于任意一对点 (u,v),都可以从 u 出发,走到 v并且回到 u

再次,强连通分量即对于这个连通分量,不能再进行点或边的拓展使其变得更大。需要注意的是,一个有向图中不一定只有一个强连通分量。只要满足不能再进行拓展的连通分量,它都是一个强连通分量。

graph

比如在这张图中,$\{1,2,3\}$ 可以互相到达,并且不能再进行拓展,所以它是一个强连通分量。$\{4\},\{5\}$ 也都分别满足要求,所以它们也分别是一个强连通分量。

而 Tarjan 算法,就可以用线性的时间求出强连通分量。


2.怎么求强连通分量?

当然是通过肉眼判断啦!

咳咳,1e6 的数据好像不太可以肉眼判断的样子。

所以我们需要一个稳定的算法能够找出所有的强连通分量。

还是以上图为例。我们对这个图进行 dfs

对于走过的边和点,我们可以构建一棵dfs 树,但这不重要,只需要知道这些点都是按 dfs 序遍历的就好了。

同时引入一个概念:时间戳。它记录的是访问点的先后顺序。用 dfn[] 记录。比如第一个访问到结点2,那么 dfn[2]=1,第二个访问到结点 1,那么 dfn[1]=2

我们可以先从点 1 走到 2,3。

但是在 3 可以走到 1 的时候我们发现这条边有点特别。为什么呢?

对于(3-1)这条边,它特殊在指向了一个比自己先遍历到的点,也就是新遍历到的点的时间戳比自己的时间戳小。很明显,在这里就构成了一个

构成了环之后,它可以通过回到的那个点,再绕一圈回到自己,这不就是连通分量的定义吗?从它向下遍历再回到自己所经过的点,都是连通分量中的点。

但是我们要找的是强联通分量。怎么办呢?

再回到这棵dfs树中。我们可以设想一下,在什么样的情况之下,我们才可以判断说某个点和它的子孙节点的某一部分构成一个连通分量呢?

当且仅当它的某个子孙节点可以连向它,并且无法连向它的祖先节点。

为什么会有后面这个限制呢?因为如果它的子孙节点可以连向它的祖先节点,这显然会构成一个更大的连通分量。

比如下面这个图:

在这个例子中,$\{2,3,4\}$ 就不是一个强联通分量,$\{1,2,3,4\}$ 才是。

所以我们需要保证这个点的子节点都不与它的祖先节点即可。

但问题来了,就算满足了这个,它的所有子节点就一定和它构成一个强连通分量吗?

明显不是。根节点就满足上面的要求,但是这棵树并不一定就全部强联通。

那么,该怎么做才能让我们在 dfs 过程中 回退到结点 $u$ 时,能知道和哪些点强联通呢?

开一个进行记录。

如果这个点和它目前已经遍历到的点形成了一个连通分量,并且它的子节点都不指向它的父亲结点时,我们只需要把 dfs 一路记录到栈里的元素挨个弹出记录即可。

所以在栈中,这个点之前弹出的点都和它在同一个强连通分量当中。


3.怎么实现求强连通分量?

先来捋一捋思路,看一下我们在基本的问题中我们需要记录哪些东西。


首先是时间戳,也就是之前提到的东西,用 dfn[]来存储。

然后,为了判断一个结点是不是可以连到某个节点的祖先节点,还要引入一个数组 low[],记录每个节点能到达的,最小时间戳结点的 时间戳。

实现栈,通过一个数组 stk[]就可以了。

in[],判断某个点是否在栈中。


接下来来一步步理解代码是如何实现的。

对了,dfs的函数名就称为 tarjan(),这里的参数只有一个 u,表示当前遍历到的结点。

因为要求是在线性的时间内求解,所以每个点都会且仅会遍历到一次。每次都是一个没有被遍历过的点。

开始!

第一步dfn[u]=low[u]=++idx;

这里用idx是因为链式前向星占用了cnt,暂且将其当做一个编号。

dfn的值赋值为 ++idx应该比较能理解,但是为什么要把 low也同样这么赋值?

回到 low的定义,它指的是一个点能到达的最小时间戳。在这个点的 low值被更新前,它所能到达的最小时间戳即为本身。

第二步in[u]=1;stk[++top]=u;

这一步是把点加入栈 没什么好说的。

第三步:遍历每一个 u连向的点 v

如果没被访问过→(!dfn[v]),那么就 tarjan(v)之后再进行一次 low[u]=min(low[u],low[v])。结合时间戳的定义,因为 v在搜索树中是 u的子节点,所以它能到达的最小时间戳可以直接和它比较。

如果被访问过,按照我们感性的认知,更新操作应该是 low[u]=min(low[u],dfn[v]),但是却不能直接这样,因为不能确定 vu一定在同一个强连通分量中。所以在这一步之前,还要加一个判断 if(in[v])

第四步:统计

如果点 u在经过它指向的点的更新之后,low[u]==dfn[u],就说明它的子孙节点都无法指向它的祖先结点,否则将有 low[u]<dfn[u]。那么就说明 u是这强连通分量的最高点,对它进行统计。

统计即挨个弹出栈里的结点,直到把 u弹出即可。

以下是核心代码块。

void tarjan(int u)
{
    dfn[u]=low[u]=++idx;
    stk[++top]=u;
    in[u]=1;
    for(int i=head[u];i;i=nxt[i])
    {
        int v=to[i];
        if(!dfn[v])
        {
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(in[v])low[u]=min(low[u],dfn[v]);
    }
  
    if(dfn[u]==low[u])
    {
        scc_cnt++;
        int k;
        do
        {
            k=stk[top--];
            in[k]=0;
            sz[scc_cnt]++;
        }
        while(k!=u);
    }
}

考虑到一个图中可能不止一个强连通分量,所以我们要遍历完所有点才能保证完成。怎么判断一个点是不是已经被 tarjan 跑过了呢?

只需要判断它的时间戳是否有被赋值即可。如果时间戳不为零(初值),那么它就是被遍历过的,否则就没有被遍历过,进行遍历。

for(int i=1;i<=n;i++)
    if(!dfn[i])tarjan(i);

另外,我们可以把一个强连通分量抽象为一个点,实现出来就是缩点操作。

以上。


二、求割点、割边(桥)

1.什么是割点、割边(桥)?

在一个无向图中,如果有一个顶点集合,删除这个顶点集合以及这个集合中所有顶点相关联的边以后,图的连通分量增多,就称这个点集为割点集合。——《百度百科》

emm...还是来捋一捋。

首先,这次研究的对象割点是存在于无向图之中的。它的特点是,去除这个点以及相关的边,原本的连通块就不再连通。

什么意思呢?

graph3.png

比如这是一个无向图,在这个图中,1,2两个点都是割点。把1去掉之后,原本的连通分量{1,2,3,4}分成了两个连通分量{3}和{2,4}。把2去掉之后则变成{1,3}和{4}。但如果对于非割点3,去掉之后还是只有一个连通分量{1,2,4},所以它不是割点。

再来看看割边的定义。

如果一个无向连通图的边连通度大于1,则称该图是边双连通的 (edge biconnected),简 称双连通或重连通。一个图有桥,当且仅当这个图的边连通度为 1,则割边集合的唯一元素 被称为桥(bridge),又叫关节边(articulationedge)。一个图可能有多个桥。(摘自百度)

2.怎么求割点?

我们需要分两种情况进行讨论。分别是根节点与非根节点。

如果一个点是根节点,它要满足什么条件才能是割点?

答案是,拥有两棵或以上的子树。这样把它去掉之后,它的多个子树会分成多个连通分量,所以根据定义,它是一个割点。

如果一个点是非根节点呢?

比如上图中的结点2,我们是如何判断出它是割点的?或者说,它作为割点,有什么特性?

不难发现,它存在一个儿子 不能到达 时间戳 比 自己 小 的结点

也就是 low[v]>=dfn[u]。在这个图里可能不太明显,我们换个图来康康。

graph4.png

看向这里的结点 2。假设当前遍历到了 2,它是非根节点。它的子节点3的 low 值明显是 1,不满足 low[v]>=dfn[u],所以 2 不是割点。

但如果变成下面这张图。

graph5.png

2的子节点6的 low 值为它的父亲 2,满足 2>=2 (low[v]>=dfn[u]),所以这时 2 就是割点。

对于判断一个点是不是根节点,只需要在遍历时多传一个参数 f 记录父亲节点即可。每次通过主程序的 for 循环进入的点就是根节点。

代码块献上。

void tarjan(int u,int f)
{
    dfn[u]=low[u]=++idx;
    int tot=0;
    for(int i=head[u];i;i=nxt[i])
    {
        int v=to[i];
        if(!dfn[v])
        {
            tot++;
            tarjan(v,u);
            low[u]=min(low[u],low[v]);
            if(u!=f&&low[v]>=dfn[u]&&!gd[u])gd[u]=1,ans++;
        }
        low[u]=min(low[u],dfn[v]);
    }
    if(u==f&&tot>1&&!gd[u])gd[u]=1,ans++;
}

模板题:割点

参考代码


3.怎么求割边?

割边的求法类似于割点.之前我们说到,在判断非根节点是否为割点时,我们采用了看 low[v]>=dfn[u]的做法,在这里我们的做法更加简单。

不需要考虑根节点的问题,只需要判定 low[v]>dfn[u](v!=f) 即可。因为保证了 v!=f,所以 low[v]!=dfn[u]。为什么可以这样判定呢?以下图为例,我们来感性理解一下:

graph5.png

假设当前遍历到结点2,它两个非父节点的儿子结点分别为3和6。回溯计算完毕之后得到 low[3]=1,low[6]=6,而 2-3不是割边,2-6是割边。

再来回顾一下 low 数组的定义吧。指的是这个点能到达的最小时间戳。如果 low[v]>dfn[u],说明 v 不能到达时间戳比 u 小的点,也就是不能到达 u的祖先节点。所以一旦割开 (u,v) 这条边,点 v 以及它的字数这一部分都将和 u分离,所以它是一条割边。

题目是入门 OJ 上的权限题...大意是求割边的数量,就只放代码了。

参考代码


? 爆肝了好几天才出来,果然还是太菜了,爬了。

最后修改:2021 年 10 月 29 日
如果觉得我的文章对你有用,请随意赞赏