发表更新OI笔记21 分钟读完 (大约3115个字)

强连通分量

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

一 定义

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} - - - - $$

强连通分量

https://big-news.cn/2019/02/07/强连通分量/

作者

ce-amtic

发布于

2019-02-07

更新于

2023-04-15

许可协议

CC BY-NC-SA 4.0

#

评论

Your browser is out-of-date!

Update your browser to view this website correctly.&npsb;Update my browser now

×

×