Tarjan 是一种求强连通分量、双连通分量的常用算法,其拓展例如求缩点、割点、割桥以及 2-SAT 等都是非常实用的。

这篇文章主要讲一下 Tarjan 的朴素算法及其在缩点、求割点等方面的应用(主要是因为其他的都不会了 QAQ

什么是强连通分量?

在有向图 G 中,如果两个顶点 vi,vj 间(vi>vj)有一条从 vi 到 vj 的有向路径,同时还有一条从 vj 到 vi 的有向路径,则称两个顶点强连通。如果有向图 G 的每两个顶点都强连通,称 G 是一个强连通图。有向图的极大强连通子图,称为强连通分量。——来自某度的解释

什么意思呢?

就是说在一个有向图中,有一个或几个子图,从它们中的任何一个点都可以到另外的任意一个点,这个子图就被称为是强连通分量(一个点也可以被称作是强连通分量哦)

另外,这张子图一定要是最大的,即要把所有满足条件的点全部加进这张子图,才能称为是强连通分量。

举个例子:

举个栗子

在这张图中,1,2,3,41,2,3,455还有66是三个强连通分量,但1,3,41,3,4并不能被称为是强连通分量,因为它不是最大的满足条件的子图,必须要加入点 2 才算。

简单介绍 Tarjan 算法

Tarjan 算法是一种基于 DFS(深度优先搜索)的求图的强连通分量的算法,非常常用(还有就是活在《信奥一本通》上的 Kosaraju 和活在百度百科中的 Gabow 算法),同时,其时间复杂度为O(n)O(n),算是非常优秀的了。

一些变量

  • tot:当前点是第几个被遍历的。

  • dfn[]:记录每个点是第几个被遍历的,可以理解为一个时间戳。

  • low[]:记录每个点不经过祖先节点能到达最早的祖先的时间戳(下称”返祖“好名字)。

    PS: 这里大部分人写的都是能到达的最早的祖先,但这样就和下面有一个公式不符,所以我改了一下,如果不对希望大佬在评论里指出,谢谢!

  • stack[]:一个栈,存放强连通分量(不是直接存哦,有一些方法的)。

  • vis[]:标记每个点是否在栈中。

  • color[]:记录每个点属于第几个强连通分量。

  • p[]:记录每个强连通分量有几个点。(最后这两个都是缩点时用的)

算法思路

  1. 从一个点出发,遍历整张图。

  2. dfn[] 数组初始化为当前点(下称 u)被遍历的顺序,同时将 u 入栈。

  3. 初始化 low[u]=dfn[u],因为一个点一定能到达它自己。

  4. 枚举所有出边(链式前向星存图),如果这条边到达的点(下称 v)还没有被遍历过,则遍历点 v,然后更新 low[u],公式为:

    low[u]=min(low[u],low[v])low[u]= \min (low[u],low[v])

    因为点 v 能到达的祖先节点,点 u 也一定能到达(废话),所以应该更新点 u 的 low 值。

    如果 v 已被遍历过,且 v 在栈中,也要更新 low 值公式为:

    low[u]=min(low[u],dfn[v])low[u]= \min (low[u],dfn[v])

    因为到达之前到过的点(也就是祖先),说明这个点可以返祖,那么肯定是要更新 low 值的(更详细的请看下面的“一些可能的问题”)

  5. 枚举完所有出边后,如果dfn[u]=low[u]dfn[u]=low[u]则说明这个点是一个强连通分量的开始点(梦开始的地方)它不可能属于其他任何一个强连通分量,因为它无法返祖,所以不可能和之前的点组成一个强连通分量,因而它属于一个独立的强连通分量,这时,将栈中在这个点之后入栈的点全部出栈(包括这个点),因为这些点也不属于其他任何一个强连通分量,如果属于,那么 u 就不可能无法返祖,所以,它们都是同一个强连通分量。

看起来很麻烦是不是?我也觉得下面用图来手模一下就清楚了。

上图:

资源缺乏,凑合着看吧

我们从点 1 开始遍历,下面是模拟过程:

  1. 从点 1 开始!u=1,dfn[1]=1,low[1]=1,stack={1},vis[1]=1u=1,dfn[1]=1,low[1]=1,stack=\{1\},vis[1]=1,先遍历点 3。
  2. u=3,dfn[3]=2,low[3]=2,stack={1,3},vis[3]=1u=3,dfn[3]=2,low[3]=2,stack=\{1,3\},vis[3]=1,再遍历点 5。
  3. u=5,dfn[5]=3,low[5]=3,stack={1,3,5},vis[5]=1u=5,dfn[5]=3,low[5]=3,stack=\{1,3,5\},vis[5]=1,遍历点 6。
  4. u=6,dfn[6]=4,low[6]=4,stack={1,3,5,6},vis[6]=1u=6,dfn[6]=4,low[6]=4,stack=\{1,3,5,6\},vis[6]=1,此时没有出边了,开始硬核出栈。
  5. 检测到dfn[6]=low[6]dfn[6]=low[6],将栈中点 6 及其之后的点全部出栈(其实只有一个点),stack={1,3,5},vis[6]=0stack=\{1,3,5\},vis[6]=066为一个强连通分量。
  6. 回溯到点 5,没有出边了,出栈。stack={1,3},vis[5]=0stack=\{1,3\},vis[5]=055为一个强连通分量。
  7. 回溯到点 3,遍历点 4。
  8. u=4,dfn[4]=5,low[4]=5,stack={1,3,4}vis[4]=1u=4,dfn[4]=5,low[4]=5,stack=\{1,3,4\}vis[4]=1,接下来遍历点 1,发现已经遍历过了,说明点 4 返祖了(!!!),此时更新low[4]=dfn[1]=1low[4]=dfn[1]=1。再遍历点 6,发现点 6 已经遍历过了,但又不在栈中,说明点 6 不属于点 4 所在的强连通分量,所以不管。此时所有出边枚举完了,回溯到点 3。
  9. 更新low[3]=min(low[3],low[4])=1low[3]=\min(low[3],low[4])=1(意思是点 3 能到达点 1),没有出边了,回溯到点 1。
  10. 遍历点 2,u=2,dis[2]=6,low[2]=6,stack={1,3,4,2},vis[2]=1u=2,dis[2]=6,low[2]=6,stack=\{1,3,4,2\},vis[2]=1,枚举出边,只有一个点 4 已经被遍历了,且点 4 在栈里,low[2]=min(low[2],dfn[4])=5low[2]=\min(low[2],dfn[4])=5,枚举完毕,回溯。
  11. 点 1 出边枚举完毕,开始出栈,stack 清空,vis 清空,1,3,4,21,3,4,2为一个强连通分量。自此,遍历完毕,三个强连通分量全部被求出(完结撒花,感谢陪伴)。

一些可能的问题

Q: 如果这张有向图不连通怎么办?也就是说,如果从一个点出发不能遍历完整张图怎么办?

A: 废话,那就从点 1 枚举到点 n,如果当前点没有被遍历过,就从这一点开始遍历。

Q: 如何判断当前点有没有被遍历过?

A: dfn 数组是干嘛的?记录每个点被遍历的顺序啊!如果 dfn 数组不为 0,则表示它已经被更新,也被遍历过了。

Q: 还是没有搞懂为什么遍历完一个点后要把 low 更新为当前点和这条边的终点的 low 值中的较小值啊。

A: low 数组记录的是能到达的最早的祖先,既然这条边的终点能到达,那起点肯定也能到达啊,同时要取最早的祖先,所以要取较小的值。

Q: 既然许多大佬都说 low[] 是记录能到的最早的祖先,那为什么出现”返祖“情况时不取祖先的能到达的最早时间戳,而要取祖先的时间戳呢?换句话说,为什么遍历到被遍历过的又在栈里的点(就是祖先嘛)时不用公式low[u]=min(low[u],low[v])low[u]= \min (low[u],low[v]),而要用公式low[u]=min(low[u],dfn[v])low[u]= \min(low[u],dfn[v])呢?

A: 这个问题其实有点复杂,理论上来说用前者是绝对没有问题的(仅限于求强连通分量的时候),但后面在求割点时,第一个公式就会出 bug,所以我将 low[] 数组定义为不经过祖先节点能到达的最早祖先,详细情况请看后面讲求割点的部分。

(大概就是这些了,如果还有什么问题后面再补充)

参考代码

题目: 洛谷 P2863 [USACO06JAN] 牛的舞会 The Cow Prom

传送门

(PS:我没有用 P2341 【模板】强连通分量 / [HAOI2006] 受欢迎的牛,是因为这道题虽然写的是强连通分量的模板,但其实还用到了缩点的知识,不便于朴素算法的理解)

题目大意: 求子图内点的个数大于 1 的强连通分量个数。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include<cstdio>
#include<cstring>
#define min(a,b) a<b?a:b
using namespace std;
struct Edge//链式前向星存图
{
int next;
int to;
};
Edge edge[50001];
int n,m,s,head[10001];
int cnt,k,ans,dfn[10001],low[10001],stack[10001],v[10001];//我这里的代码时间和这篇笔记的时间隔了将近 5 天
//所以有些变量名可能不太一样
//这里 v 数组就是上面的 vis
//cnt 是上面的 tot
void tarjan(int x)
{
cnt++;
dfn[x]=low[x]=cnt;
stack[++k]=x;
v[x]=1;//初始化各种数组,包括 dfn 和 low 初始化为 x 被遍历到的次序,x 入栈,v 标记 x 入栈
for(int i=head[x];i!=-1;i=edge[i].next)
if(!dfn[edge[i].to])//如果没有搜过
{
tarjan(edge[i].to);
low[x]=min(low[x],low[edge[i].to]);//取自己能到的最早祖先和终点能到的最早祖先
}
else
if(v[edge[i].to])//如果搜过了,且这个点在栈里,说明返祖了
low[x]=min(low[x],dfn[edge[i].to]);//详情见上面
if(dfn[x]==low[x])//如果 dfn[x]=low[x],说明这个点为整个强连通分量中的最老的祖先,也说明整个强连通分量已经遍历完了
{
int flag=0;
while(stack[k]!=x)
{
flag=1;
v[stack[k]]=0;
k--;
}
v[x]=0;
k--;
if(flag)//这里是判断这个强连通分量点的个数是否大于 1(题目要求)
ans++;
}
}
void add_edge(int u,int v)
{
edge[s].next=head[u];
edge[s].to=v;
head[u]=s;
s++;
}
int main()
{
memset(head,-1,sizeof(head));
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int a,b;
scanf("%d%d",&a,&b);
add_edge(a,b);
}
for(int i=1;i<=n;i++)
if(!dfn[i])
tarjan(i);//不确定从一个点开始就能遍历完整张图,所以要每个点都试一下
printf("%d",ans);
return 0;
}

Tarjan+缩点

What means 缩点?

一张有向图中,如果存在环,就会造成很多不方便的地方,比如不方便进行动归计算,这时,就可以用缩点来解决问题,所谓缩点,就是将这张有向图中所有的强连通分量变成一个一个的团,然后给这些团加边,形成一张 DAG(有向无环图),就便于解决问题了。

这张图会让你更明白一些:

这张图中共有四个强连通分量,已经用红色圈出来了,对其进行缩点操作以后,就会变成下面这个样子:

是不是很棒棒啊仔细研究一番以后,可以发现:点 1 对应强连通分量1,2,3,41,2,3,4,点 2 对应强连通分量8,98,9,点 3 对应强连通分量5,6,75,6,7,点 4 对应强连通分量1010,此时,这张图中已经不存在环了,可以放心地尽情搞♂事♂情。

算法思路

  1. Tarjan 求出强连通分量,并在出栈时更新 color 和 p。
  2. 遍历所有边,如果这条边连接的两个点不在同一个强连通分量中,就连边。

看起来很简单是不?没错,就是这么简单,没有别的了,只是有些细节可以再优化一下,下面的代码中会讲到。

参考代码

题目: 洛谷 P3387 【模板】缩点

传送门

题目大意: 将一张有向图缩点,然后在新的图上跑一遍记忆化 DFS(DP 也行),求出一条经过的点权值和最大的路径。

为什么知道这道题是缩点呢?废话这题目写了是缩点模板的嘛

既然题目告诉我们,可以重复经过一个点或一条边,但权值只计算一次,那么,既然是同一个强连通分量,取了一个,为什么不能取其他的呢?反正可以重复经过,取完一个强连通分量再回到之前的点就行了,完全不影响啊,这样缩完点后,一个强连通分量就是一个点,到达这个点,相当于就是到达了整个强连通分量,同时,在 DAG 图上跑记忆化,可以做到O(n)O(n)啊,如果不缩点,那就要重复经过一个点,这样时间复杂度就大大提升了,所以为什么不先用 Tarjan 跑一遍O(n)O(n),再用记忆化跑一遍O(n)O(n)呢,这样更优啊。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct Edge
{
int next;
int to;
};
Edge edge[100001];
int x[100001],y[100001];
int n,m,s,a[10001],head[10001];
int cnt,cur,top,dfn[10001],low[10001],stack[10001],v[10001];//cur 是统计强连通分量个数的
int np[10001],b[10001];//这里的 np 相当于是上面的 p,b 则是 color
int ans,f[10001];//f[i] 记录的是从第 i 个强连通分量开始遍历所能取到的最大值
void add_edge(int u,int v)
{
edge[s].next=head[u];
edge[s].to=v;
head[u]=s;
s++;
}
void tarjan(int x)
{
cnt++;
dfn[x]=low[x]=cnt;
stack[++top]=x;
v[x]=1;
for(int i=head[x];i!=-1;i=edge[i].next)
if(!dfn[edge[i].to])
{
tarjan(edge[i].to);
low[x]=min(low[x],low[edge[i].to]);
}
else
if(v[edge[i].to])
low[x]=min(low[x],dfn[edge[i].to]);
if(dfn[x]==low[x])
{
cur++;//当前强连通分量遍历完毕,cur 加一
while(stack[top+1]!=x)//这里之所以用 top+1 是为了把 x 也弹出来
{
v[stack[top]]=0;
b[stack[top]]=cur;//标记栈顶的点属于第 cur 个强连通分量
np[cur]+=a[stack[top]];//p 为这一强连通分量中所有点权值之和
top--;
}
}
}
void dfs(int x)
{
if(f[x])
return;//搜过了,就不再搜了
int maxn=np[x];
for(int i=head[x];i!=-1;i=edge[i].next)
{
if(!f[edge[i].to])
dfs(edge[i].to);
maxn=max(maxn,f[edge[i].to]+np[x]);//取所有出边的终点中 f 的最大值
}
f[x]=maxn;
}
int main()
{
memset(head,-1,sizeof(head));
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=1;i<=m;i++)
{
scanf("%d%d",&x[i],&y[i]);
add_edge(x[i],y[i]);//优化:将之前的边存下来,便于后面重新建图
}
for(int i=1;i<=n;i++)
if(!dfn[i])
tarjan(i);
memset(head,-1,sizeof(head));
memset(edge,0,sizeof(edge));
s=0;
for(int i=1;i<=m;i++)//为什么不用链式前向星遍历:为了节省内存,我们将之前的 edge 清空
//因为链式前向星不是线性存图,所以一边遍历 edge 一边用 edge 来存图会冲突
if(b[x[i]]!=b[y[i]])//b[x[i]] 和 b[y[i]] 分别表示 x[i] 和 y[i] 所在的强连通分量
add_edge(b[x[i]],b[y[i]]);//添加第 b[x[i]] 个强连通分量和第 b[y[i]] 个强连通分量之间的边
for(int i=1;i<=cur;i++)//缩点后的图不一定从一点出发就能到达所有的点,因此要一个一个枚举
{
dfs(i);//记忆化深搜
ans=max(ans,f[i]);
}
printf("%d",ans);
return 0;
}

Tarjan+割点

何为割点?

在一张无向图中,有一个或几个点,删去之后整张图就不连通了,这样的点称为割点,也就是说,如果没有这个点,一张连通图就会变成几张连通图。

还是举个例子:

举个栗子

在这张无向图中,很容易看出,如果删去点 3,整张图就会变成1,21,24,5,64,5,6两张连通图,因此,点 3 为这张无向图的割点,同时,如果删去点 4,整张图会变成1,2,31,2,35,65,6两张连通图,因此,点 4 也是这张图的割点。

算法思路

  1. 从一个根节点出发,遍历全图。

  2. 一边遍历,一边判断当前点是否为割点。

    关于如何判断割点,我们分成两部分来考虑。

    1. 如果这个点是根节点,那好办,如果它连接两个及以上的连通图,这个点就是割点,因为如果去掉这一点,这些连通图就不连通了(之所以会有两张及以上的连通图,就是因为这些图彼此两两不连通,而只通过根节点连接彼此,所以,如果根节点炸了,这些图就失去了唯一的连通途径,就不连通了)

    2. 如果这个点不是根节点,就要判断它下面的点不通过它能否返祖,如果全都可以,则这个点不为割点,因为它的儿子都可以不通过它返祖,那要它也没什么用,但只要有一个儿子必须经过它才能返祖,这个点就是割点,因为去掉它后它的儿子就不能与上面的图连通。

      如何判断?

      用这个!if(low[v]dfn[u])if(low[v]\ge dfn[u]),low 记录的是不经过祖先节点所能访问到的最早的祖先的时间戳,如果儿子的 low 值比当前节点的时间戳要小(或正好等于它),就说明这个儿子不经过它,是无法访问到更早的点的,所以去掉这个点后,它的儿子和祖先节点的连接就会断掉,就不连通了,所以这个点是割点。

      用图来模拟一下好了。

      Tarjan 图 5.png

      我们从点 1 开始遍历,因此点 1 为根节点,它连接了两张连通图(即2,3,42,3,455),如果它炸了,两张连通图就不再相互连通,所以它是割点。再看点 2,因为点 3 和点 4 不经过点 2 就无法访问点 1,所以,点 2 如果炸了,点 3 和点 4 就不能与点 1 连通,所以点 2 也是割点。

一个非常重要的地方

这里就可以看出为什么当遍历时遇到祖先节点时的公式为low[u]=min(low[u],dfn[v])low[u]=\min(low[u],dfn[v])而不是low[u]=min(low[u],low[v])low[u]=\min(low[u],low[v])了,因为如果是后者的话则计算的是不管怎样到,总之能到达的最早的祖先,这样无法判断这个点最直接的能回到的祖先,也就无法判断割点。在上面的图中,如果用后面那个公式,low[3] 和 low[4] 就都会变成 1,此时再判断点 2,就不能看出点 2 是割点了。

参考代码

题目: 洛谷 P3388 【模板】割点(割顶)

传送门

题目大意: 求一张无向图中的割点(注意:是从小到大输出节点!)

参考代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct Edge
{
int next;
int to;
};
Edge edge[200001];
int n,m,s,head[20001];
int cnt,top,cur,dfn[20001],low[20001],stack[20001],v[20001],b[20001];//b 用来存放割点
void add_edge(int u,int v)
{
edge[s].next=head[u];
edge[s].to=v;
head[u]=s;
s++;
}
void tarjan(int x,int root)//root 是当前连通图的根节点,也就是最先被遍历的那个点
{
int son_cnt=0,flag=0;//son_cnt 统计连接的连通图个数
cnt++;
dfn[x]=low[x]=cnt;
stack[++top]=x;
v[x]=1;
for(int i=head[x];i!=-1;i=edge[i].next)
if(!dfn[edge[i].to])
{
tarjan(edge[i].to,root);
low[x]=min(low[x],low[edge[i].to]);
if(low[edge[i].to]>=dfn[x]&&x!=root)
flag=1;
if(x==root)
son_cnt++;//遍历完一个点后,这个点所在的连通图也就遍历完了,所以加一
}
else
if(v[edge[i].to])
low[x]=min(low[x],dfn[edge[i].to]);//注意!原因上面讲过了,不这样写的话就会 WA
if(son_cnt>=2)//如果连接的连通图个数大于一,则这个点为割点
flag=1;
if(flag)
b[++cur]=x;
if(dfn[x]!=low[x])
while(stack[top+1]!=x)
{
v[stack[top]]=0;
top--;
}
}
int main()
{
memset(head,-1,sizeof(head));
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
add_edge(x,y);
add_edge(y,x);//无向图要添加两条边
}
for(int i=1;i<=n;i++)
if(!dfn[i])
tarjan(i,i);//枚举所有点,如果没有被遍历过,就从这一点开始遍历
sort(b+1,b+1+cur);//排序!!
printf("%d\n",cur);
for(int i=1;i<=cur;i++)
printf("%d ",b[i]);
return 0;
}

总结

Tarjan 算法真的很常用,而且应该算是比较难的一个东西了,它有很多应用,还有很多的扩展,所以一定要把最基础的东西弄牢固,否则会对后面的练习造成困难。

一些相关的题目

洛谷 P1656 炸铁路(割边,与割点的求法有一个很小的不同,看一下题解就知道了)

洛谷 P2341 【模板】强连通分量 / [HAOI2006] 受欢迎的牛(缩点)

洛谷 P2746 [USACO5.3] 校园网 Network of Schools(缩点,有点考智商)

洛谷 P3469 [POI2008]BLO-Blockade(有难度的割点+数学)

洛谷 P5058 [ZJOI2004] 嗅探器(有些难度的割点)