强连通分量

这篇会写强连通分量的介绍和两种算法应用

目录

• 1.定义和基本性质
• 2.核心算法
• • 2.1 Tarjan算法
• • 2.2 Kosaraju算法

一. 定义与基本性质

强连通分量广泛用于各种题型
定义
强连通图:一个有向图G中 对于任意两个顶点 u, v. 存在 u 到 v 的路径 也存在 v 到 u 的路径, 则该图为强连通图
强连通分量(SCC)是有向图G中的一个极大强连通子图
极大:不能再向里面加入更多顶点 依然保持强连通
注意 极大不等于最大 最大是顶点数最多的那个, 极大是在这个范围里我最大, 再往外扩一步就崩了

原图G中将每个强连通分量缩为一个点 就得到一个新有向无环图(DAG) G’ 也称为缩点图
(因为不同 SCC 之间不可能互相可达, 否则就属于同一个 SCC, 所以缩点后一定无环)

二. 核心算法

例题:洛谷B3609

2.1 Tarjan算法

对有向图做dfs 每条边分为四种:

• 树边: 第一次发现新节点走的边
• 后向边: 指向祖先节点的边 (在dfs树中向上)
• 前向边: 指向后代节点且非树边
• 横叉边: 连接不同子树分支的边 (不是祖先关系也不是后代关系)

前两种比较好理解 后两种举个例子:

A---/|B|/|C<--------

A->C这条边 若C节点已访问 且是A的后代 但不是直接的儿子(直接的儿子是树边) 即这条边是前向边

D/\ F<-E

E->F这条边 若F已访问 两个节点不是祖先也不是后代 这条边为横叉边
注意: 边的分类不是一个图固有的 是由dfs遍历顺序决定的 即同一个图不同的dfs树 任意节点的关系可以完全不同

回到算法本身
定义dfn和low

• dfn[u]: 节点 u 被首次访问的时间戳(即dfs序)
• low[u]: 在dfs树中 以u为根的子树中的节点,通过至多一条非树边(后向边or横叉边)能够到达的仍在栈中的最早节点的dfn (这里定义相对严格)
  通俗的说, low[u]就是 u 所在dfs子树能勾搭到的最老的还在栈里的祖先or兄弟的时间戳
  我们从 u 节点开始 一直向下寻找 直到有一个节点告诉我们 “我能找到在栈中的祖先了” 那么记录自己的low 接连返回一直到找到了这个祖先也就是这棵SCC的根

由此, 若dfn[u] == low[u] 说明u能到达的祖先节点是自己 即是这棵SCC的根

1. 遍历u的出边

• 若dfn[v]==0(v未被访问)
  进入递归
  low[u] = min(low[u], low[v]) (子树通过 v 能勾搭到的上古节点, u 同样能)
• 否则 v以访问且还在栈中的话
  low[u] = min(low[u], dfn[v]) (v 是栈中节点, 边是一条后向边或横叉边, 直接用 v 的 dfn 更新 low[u])

2. 遍历完出边后 若dfn[u] == low[u] 记录答案SCC

过程

vector<int>dfn,low;intinstack[N];// 节点u是否在栈中stack<int>stk;// 暂存为确定强连通分量的节点vector<vector<int>>sccs;//结果 每个元素是一个强连通分量inttimer;//时间戳计数器voidTarjan(intu){dfn[u]=low[u]=++timer;stk.push(u);instack[u]=1;for(intv:g[u]){if(dfn[v]==0){// 接着往深了走Tarjan(v);low[u]=min(low[u],low[v]);}elseif(instack[v]){// u节点能到栈中的v了 即祖先low[u]=min(low[u],dfn[v]);}}if(dfn[u]==low[u]){// 祖先找到了 依次弹出来vector<int>cnt;while(1){intv=stk.top();stk.pop();instack[v]=0;cnt.push_back(v);if(v==u)break;//直到祖先也被弹出来了 证明一个SCC剥离完了}sccs.push_back(cnt);}signedmain(){for(i1-n){if(dfn[i]==0)Tarjan(i);}}

low的定义是通过至多一条非树边能到达的最早dfn
为什么对已访问且在栈中的节点, 用 dfn[v] 更新而不是用 low[v]?
第二天我思考了一下
这里给一个例子:
1 -> 2 -> 3 -> 1
step1从节点1出发
踏进1, dfn[1] = 1, low[1] = 1 把1压入栈 stack = [1]
看1的儿子: 有2 dfn[2] == 0 没去过
递归进入2
step2进入节点2
踏进2, dfn[2] = 2 low[2] = 2 压栈 stack = [1, 2]
2的儿子有3 dfn[3] == 0 没去过
递归进入3。
step3进入节点3
踏进3, dfn[3] = 3 low[3] = 3 压栈 stack = [1, 2, 3]
3的儿子 有1但
dfn[1] != 0, dfn[1] = 1
检查1在不在栈里 在.(stack = [1,2,3])
因为找到了一个非树边(后向边)指向了栈中祖先1 所以 low[3] = min(low[3]=3, dfn[1]=1) = 1

此时3处理完毕 回溯:
low[2] = min(low[2], low[3]) = 1
low[1] = min(low[1], low[2]) = 1
好 这时候low[1] = dfn[1] 这是找着大祖先了 是SCC的根 此时依次出栈 一直出到祖先的位置 此时出去的都是一个SCC的

例子举完了
那个问题: 为什么对已访问且在栈中的节点, 用 dfn[v] 更新而不是用 low[v]?
若只专注于定义本身理解:
low[u]要求u到子树中的节点经过至多一条非树边若使用low[v]来更新 因为low[v]本身含带经过至多一条非树边的信息 而且v已经被访问 若使用low[v]会导致low[u]的含义变成至多两条非树边 违背了对于low数组的定义

而从理论上理解:
从我们进入Tarjan的第一个节点开始 这个dfs就在无限开始往深了递归 low的定义规定了我们上文所描述的一个节点(可以到达栈中的祖先) 而想满足这点 只能是通过至多一条非树边(要么是形成环到了祖先(后向边) 要么是祖先是我的兄弟(横叉边)) 否则 若是通过多个非树边 找到的就不是栈中祖先的dfn了 而是目前节点能到达的祖先能到达的它的祖先节点的dfn 明显不对 直觉上讲容易把scc混成一起 虽说理论上当前节点能到的祖先的祖先和当前节点应该共属一个scc 但从对scc的定义上和正确直觉上 明显是要用能到达的祖先的dfn 也就是只经过一条非树边的祖先 不仅是为了遵守局部推导的理论事实 同时也是防止"瞎跳" 我跳到祖先的祖先这谁知道在哪
时间复杂度O(n+m)每个节点和每条边只被访问常数次

2.2 Kosaraju 算法

原理: 一个图里 每条边反向 就得到了反图 原图和反图的强连通分量完全一样于是先在原图上做dfs 记录节点离开的时间(后序) 然后在反图按离开时间从晚到早再来一把dfs 每次能从某个起点访问到的节点 就是一个SCC
证明
1.反图的SCC不变在有向图中 顶点uv是否属于同一个SCC条件是是否互相可达 明显 边反过来还是一样可达
2.为什么按照离开时间从晚到早把原图转换为缩点图一个缩点图一定有出度为0的节点 当第一次dfs时 最后离开的节点的时间戳就是拓补序的最后 也就是属于出度为0的那个SCC 我们按照逆序时间戳遍历 即按照逆拓补序 从出度为0的SCC开始一层层分离SCC
补充:离开时间可看下面的dfs1理解 对于一个u->v 离开时间为vu 反向跑反图相当于从u开始 u能跑到v证明有一条u->v 又因为这是反图所以原图有一条u<-v 那么这两个共属同一个SCC 这么说可能好理解点因为我写完这篇笔记第二天又看不懂我自己写的了

vector<int>g[N],reg[N];// 原图和反图intvis[N];// 标记数组vector<int>order;// 记录离开顺序vector<vector<int>>sccres;//scc的答案//dfs1记录离开顺序voiddfs1(intu){vis[u]=1;for(intv:g[u]){if(!vis[v])dfs1(v);}order.push_back(u);}//dfs2找一个sccvector<int>cnt;voiddfs2(intu){vis[u]=1;cnt.push_back(u);for(intv:reg[u]){if(!vis[v])dfs2(v);}}signedmain(){//第一次dfsfor(inti=0;i<n;i++){if(!vis[i])dfs1(i);}//逆序遍历ordermemset(vis,0);for(inti=n-1;i>=0;i--){intu=order[i];if(!vis[u]){cnt.clear();dfs2(u);sccres.push_back(cnt);}}return0;}

时间复杂度O(n+m) 两次dfs, 每个节点和每条边访问常数次

三.总结

若给的图不大 那么kosaraju最稳 若追求效率则Tarjan 但是两种其实都很好用