强连通分量

强连通分量

Tarjan陪伴强连通分量,
生成树完成后思路才闪光。
Euler跑过的七桥古塘
让你,心驰神往……

封面图来自unsplash.com

一 定义

1 强连通

在有向图 $ G $ 中,选出 $ n $ 个点,使得这些点两两可达,则称这些点强连通

有向图 $ G $ 上强连通的的顶点,被称为 $ G $ 的强连通子图
显然,一个有向环上的点一定是强连通的(或说强连通子图中一定存在一个环)。

若 $ G $ 整体强连通,则称 $ G $ 为一个强连通图

2 强连通分量

在非强连通图 $ G’ $ 中,极大强连通子图称为 $ G’ $ 的强连通分量(Strongly Connected Components,SCC)。注意极大的概念,它强调相对于自身无法继续扩大。

如下图,SCC有 $ \begin{Bmatrix}1,2,3,4\end{Bmatrix} $ , $ \begin{Bmatrix}5\end{Bmatrix} $ 和 $ \begin{Bmatrix}6\end{Bmatrix} $ 。其中强连通子图还有 $ \begin{Bmatrix}1,3,4\end{Bmatrix} $ ,但是它不“极大”(因为它还可以扩大为 $ \begin{Bmatrix}1,2,3,4\end{Bmatrix} $ ),所以不是SCC。

1.2.1


二 Tarjan算法

Robert Tarjan(1984~),美帝人,计算机科学家,以LCA、强连通分量等算法闻名。

1 dfs树

学习tarjan的玄学算法,我们首先要了解dfs树,即把一张有向连通图转化为一棵搜索树。

树上的一些定义:

  • $ \text{dfn} $ (dfs number):结点第一次被访问的时间(起点为 $ 1 $ ,每次搜索 $ +1 $ )
  • $ \text{low} $ :结点所能到达的最小 $ \text{dfn} $ 值
  • 树边:dfs树上应有的边,又父节点指向子节点
  • 返祖边:dfs树上不应有的边,且该边由子辈节点指向父辈节点(注意这里不一定是父子节点)
  • 横叉边:dfs树上不应有的边,且该边连接的两个点无父子辈关系(注意横叉边一定由 $ \text{dfn} $ 值大的节点指向 $ \text{dfn} $ 值小的节点,否则它是树边)

上图的dfs树,以 $ 1 $ 为起点。
2.1.1
图中 $ 5 $ 节点的 $ \text{low} $ 值为 $ 5 $ 而不是 $ 4 $ ,是因为横插边 $ (5,6) $ 会被忽略,下面会讲。

2 处理思路

SCC中一定存在若干个环,那么我们可以通过找环来判断是否找到了SCC。

2-1 怎么判断环的有无

当存在一个节点 $ u $ ,使得 $ \text{dfn}[u] = \text{low}[u] $ 时,那么就发现了一个环。从定义看,这代表从当前节点出发能到达的最早的祖先是当前节点,也就是说递归“绕回来了”,那么就一定存在环。这个环也包括自环,这需要默认每个节点初始状态下都存在自环,即初始化 $ \text{low}[u] = \text{dfn}[u] $ 。

那么剩下的问题就是怎么计算 $ \text{low}[u] $
假设存在边 $ (u,v) $ ,那么这条边有以下三种可能。

  1. 边 $ (u,v) $ 为树边。那么向下dfs节点 $ v $ , $ \text{low}[u] $ 可由 $ \text{low}[v] $ 推得,即 $ \text{low}[u] = \text{low}[v] $ 。
  2. 边 $ (u,v) $ 为返祖边。根据 $ \text{low} $ 的定义,直接更新 $ \text{low}[u] $ ,即 $ \text{low}[u] = \text{dfn}[v] $ 。此处也可以直接令 $ \text{low}[u] = \text{low}[v] $ ,因为 $ v $ 能到达的的祖先也可以被 $ u $ 到达,通过多条返祖边即可。
  3. 边 $ (u,v) $ 为横叉边。此时分情况处理,详见二.2-3

2-2 怎么维护SCC

判环只能发现SCC,我们还需要维护SCC中的节点。

考虑用一个栈(stack)来实现。
每次深搜时,把节点的编号入栈。回溯时,仅当某节点处出现环,且子树都检索完毕(也就是说子树中所有不在环上的点都已经 入/出栈 完成),此时出栈至该节点为止。那么此时该节点以上的所有栈内元素均可以互达,均在一个环上,均属同一个SCC。

2-3 怎么处理横叉边

假设当前节点为 $ u $ ,有一条到 $ v $ 的横叉边 $ (u,v) $ 。
如果从 $ v $ 处出发,能直接或间接地到达 $ u,v $ 的公共祖先(不一定最近),那么这条横叉边应该被重视,因为这样就会出现环。反之,这条横叉边就应该被忽略。

假设存在一条返祖边 $ (v,a) $ , $ a $ 为 $ v $ 能回到的最远祖先。
那么当 $ u $ 在以 $ a $ 为根的子树中时,横叉边被重视,反之被忽略。

再看上述维护方法:
当 $ u $ 不在以 $ a $ 为根的子树中,当检索到 $ u $ 时,因为横叉边一定从后访问的节点指向先访问的节点,那么 $ v $ 一定被检索过。 $ a $ 是 $ v $ 的祖先,那么子树 $ a $ 一定已经检索完成。因为存在返祖边 $ (v,a) $ ,所以此时存在从 $ a $ 出发的环,那么子树 $ a $ 必然已经出栈,此时 $ v $ 不在栈内。

同理可知,若 $ u $ 在以 $ a $ 为根的子树中,则此时 $ v $ 一定在栈内。于是我们可以知道,当且仅当 $ v $ 在栈内时,横叉边 $ (u,v) $ 应被重视,需要更新 $ \text{low}[u] = \text{low}[v] $ ,回答了上文二.2-1中留下的问题。

3 流程

手推对于上图的 tarjan 算法。代码见二.4

Step 1
扫描到节点 $ 1 $ ,节点入栈。

cde 1 2 3 4 5 6
dfn 1 n/a n/a n/a n/a n/a
low 1 n/a n/a n/a n/a n/a
stack 1

Step 2
访问边 $ (1,2) $ ,扫描到节点 $ 2 $ ,节点入栈。

cde 1 2 3 4 5 6
dfn 1 2 n/a n/a n/a n/a
low 1 2 n/a n/a n/a n/a
stack 1 2

Step 3
访问边 $ (2,4) $ ,扫描到节点 $ 4 $ ,节点入栈。

cde 1 2 3 4 5 6
dfn 1 2 n/a 3 n/a n/a
low 1 2 n/a 3 n/a n/a
stack 1 2 4

Step 4
访问边 $ (4,6) $ ,扫描到节点 $ 6 $ ,节点入栈。

cde 1 2 3 4 5 6
dfn 1 2 n/a 3 n/a 4
low 1 2 n/a 3 n/a 4
stack 1 2 4 6

Step 5
节点 $ 6 $ 无出度,且存在自环( $ dfn[6]=low[6] $ ),出栈至节点 $ 6 $ ,回溯至节点 $ 4 $ 。

cde 1 2 3 4 5 6
dfn 1 2 n/a 3 n/a 4
low 1 2 n/a 3 n/a 4
stack 1 2 4

发现强连通分量 $ {6} $

Step 6
发现返祖边 $ (4,1) $ ,更新 $ 4 $ 的 $ \text{low} $ 值,不出栈并回溯至节点 $ 2 $ 。

$ 2 $ 的 $ \text{low} $ 值更新。

cde 1 2 3 4 5 6
dfn 1 2 n/a 3 n/a 4
low 1 1 n/a 1 n/a 4
stack 1 2 4

Step 7
发现边 $ (2,5) $ ,扫描至节点 $ 5 $ ,入栈。

cde 1 2 3 4 5 6
dfn 1 2 n/a 3 5 4
low 1 1 n/a 1 5 4
stack 1 2 4 5

Step 8
发现横叉边 $ (5,6) $ ,此时 $ 6 $ 不在栈内,忽略该横叉边。出栈至节点 $ 5 $ ,回溯至节点 $ 2 $ 。

cde 1 2 3 4 5 6
dfn 1 2 n/a 3 5 4
low 1 1 n/a 1 5 4
stack 1 2 4

发现强连通分量 $ {5} $

Step 9
回溯至节点 $ 1 $ ,扫描边 $ (1,3) $ ,节点 $ 3 $ 入栈。

cde 1 2 3 4 5 6
dfn 1 2 6 3 5 4
low 1 1 6 1 5 4
stack 1 2 4 3

Step 10
发现横叉边 $ (3,4) $ ,此时 $ 4 $ 在栈内,用 $ 4 $ 的 $ \text{low} $ 值更新 $ 3 $ 的 $ \text{low} $ 值。

cde 1 2 3 4 5 6
dfn 1 2 6 3 5 4
low 1 1 1 1 5 4
stack 1 2 4 3

Final
回溯至节点 $ 1 $ ,出栈至栈空,算法结束。

cde 1 2 3 4 5 6
dfn 1 2 6 3 5 4
low 1 1 1 1 5 4
stack

发现强连通分量 $ {1,2,3,4} $

4 代码实现

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
const int CP=1e3+3;

int dfn[CP],low[CP],idx=0,stk[CP],top=0;
bool ins[CP]; // 是否在栈中
int ans=0;
void tarjan(int cur){
dfn[cur] = low[cur] = ++idx; //设置初始值
stk[++top] = cur; ins[cur] = true; //节点入栈

for(int k=hd[cur]; k; k=E[k].nxt){ //遍历边表
int to=E[k].to; //边的终点
if(!dfn[to]){ //未被访问,说明这是树边
tarjan(to); //深搜
low[cur] = min(low[cur], low[to]);
}
else if(ins[to]) //已经访问且在栈内,说明这是返祖边或需要重视的横叉边
low[cur] = min(low[cur], low[to]); //此处写成low[cur] = min(low[cur], dfn[to])也没有问题
}

if(dfn[cur] == low[cur]){ //发现环
ans++; //计数
while(true){
int pos=stk[top--];
ins[pos] = false; //标记去除
if(pos == cur) break; //出栈至当前节点
}
}
}

void scc(){ //主求解函数
for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i);
}

三 缩点

1 模型

给定一张有向图 $ G_0 $ ,不保证无环,图上的节点有点权(正权,注意无法处理负环),要求找一条从起点到终点的路径,使得经过节点的点权和存在最大值。对于每条边,可以走多次。对于每个节点,点权仅计算一次。

怎么解决呢?

先考虑无环时的情况,那么只需要一遍DP(记忆化搜索)就可以解决问题。
再考虑环。对于任意一个环,如果走这个环,那么一定要全走才能获得最大价值,也就是一条环的价值可以被看作一个点的价值。一条环一定是强连通的,那么我们只需要求出 $ G_0 $ 的所有的强连通子图,分别统计它们的点权(累加环上点权和),并重新建图连边。
于是我们会得到一个有向无环图(Directed Acyclic Graph,DAG)。借用无环时的解决方案即可解决问题。

2 代码实现

边表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class fs{
public:
int to,nxt;
}E[CON];
int hd[CON],cnt=0;
void E_add(int x,int y){
E[++cnt].to=y;
E[cnt].nxt=hd[x];
hd[x]=cnt;
}
void E_init(){
memset(hd,0,sizeof(hd));
memset(E,0,sizeof(E));
cnt=0;
}

算法

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
int dfn[CON],low[CON],idx=0,stk[CON],top=0,belong[CON];
bool ins[CON];
void tarjan(int cur){
dfn[cur] = low[cur] = ++idx;
stk[++top] = cur; ins[cur] = true;

for(int k=hd[cur]; k; k=E[k].nxt) {
int to=E[k].to;
if(!dfn[to]){
tarjan(to);
low[cur] = min(low[cur], low[to]);
}
else if(ins[to]) low[cur] = min(low[cur], low[to]);
}

if(dfn[cur] == low[cur]){ //出现环,则定义cur为当前环的根(因为它先被扫描到)
int sum=0;
while(true){
int pos = stk[top--]; ins[pos] = false;
sum += c[pos];
c[pos] = 0; //这样不是根的节点c值一定为0
belong[pos] = cur; //染色,即记录环的根
if(pos==cur) break;
}
c[cur] = sum; //将环上点的权值累加入根的权值
}
}
void scc(){ //主求解函数
for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i);
}

//dp
int f[CON]; //f[i]为从i出发的最优解
int dp(int cur){ //记忆化搜索
if(f[cur]) return f[cur];
f[cur] = c[cur]; //初始化
for(int k=hd[cur]; k; k=E[k].nxt)
f[cur] = max(f[cur], dp(E[k].to)+c[cur]); //转移方程
return f[cur];//返回解
}
int solve(){
E_init(); //边表初始化
for(int i=1;i<=m;i++)
if(belong[x[i]] != belong[y[i]]) //不在一个环上,避免连出自环边
E_add(belong[x[i]], belong[y[i]]); //将两个强连通子图的根连边。原图中x[i]->y[i]存在边

int ans=0;
for(int i=1;i<=n;i++) //枚举起点
if(c[i]) ans=max(ans, dp(i)); //是根,更新答案

return ans;
}

3 推论

设一有向联通图缩点后得到图 $ G’ $ ,且在 $ G’ $ 中,入度为 $ 0 $ 的点(DAG的起点)有 $ x $ 个,出度为 $ 0 $ 的点(DAG的终点)有 $ y $ 个。

  1. 图 $ G’ $ 必为一个DAG。
  2. 选出最少的点,使得从这些点出发,可以到达整个图。则这个最小值一定为 $ x $ 。(必要性:不从起点出发那么起点永远无法到达。 最优性:考虑任意一个非起点的点,从它出发一定比从它的起点出发覆盖的节点少。)
  3. 选出最少的点,使得从任意点出发,可以到达这些点。则这个最小值一定为 $ y $ 。(必要性:终点本身无法到达任何点,那么不选中终点显然是不合法的。 最优性:终点既然必定选中,且选中所有终点一定合法,那么不需要再选中其它点。)
  4. 添加最少的边,使得 $ G’ $ 成为一个强连通图,则这个最小值一定为 $ \max x,y $ 。(考虑终点向起点对应连边。)

$$ - - - - \mathcal{End} - - - - $$

最近更新: 2019-4-9 梳理了部分不清楚的描述。


评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×