强连通分量这篇会写强连通分量的介绍和两种算法应用目录1.定义和基本性质2.核心算法2.1 Tarjan算法2.2 Kosaraju算法一. 定义与基本性质强连通分量广泛用于各种题型定义强连通图:一个有向图G中 对于任意两个顶点 u, v. 存在 u 到 v 的路径 也存在 v 到 u 的路径, 则该图为强连通图强连通分量(SCC)是有向图G中的一个极大强连通子图极大:不能再向里面加入更多顶点 依然保持强连通注意 极大不等于最大 最大是顶点数最多的那个, 极大是在这个范围里我最大, 再往外扩一步就崩了原图G中将每个强连通分量缩为一个点 就得到一个新有向无环图(DAG) G’ 也称为缩点图(因为不同 SCC 之间不可能互相可达, 否则就属于同一个 SCC, 所以缩点后一定无环)二. 核心算法例题:洛谷B36092.1 Tarjan算法对有向图做dfs 每条边分为四种:树边: 第一次发现新节点走的边后向边: 指向祖先节点的边 (在dfs树中向上)前向边: 指向后代节点且非树边横叉边: 连接不同子树分支的边 (不是祖先关系也不是后代关系)前两种比较好理解 后两种举个例子:A---/|B|/|C--------A-C这条边 若C节点已访问 且是A的后代 但不是直接的儿子(直接的儿子是树边) 即这条边是前向边D/\ F-EE-F这条边 若F已访问 两个节点不是祖先也不是后代 这条边为横叉边注意: 边的分类不是一个图固有的 是由dfs遍历顺序决定的 即同一个图不同的dfs树 任意节点的关系可以完全不同回到算法本身定义dfn和lowdfn[u]: 节点 u 被首次访问的时间戳(即dfs序)low[u]: 在dfs树中 以u为根的子树中的节点,通过至多一条非树边(后向边or横叉边)能够到达的仍在栈中的最早节点的dfn (这里定义相对严格)通俗的说, low[u]就是 u 所在dfs子树能勾搭到的最老的还在栈里的祖先or兄弟的时间戳我们从 u 节点开始 一直向下寻找 直到有一个节点告诉我们 “我能找到在栈中的祖先了” 那么记录自己的low 接连返回一直到找到了这个祖先也就是这棵SCC的根由此, 若dfn[u] low[u] 说明u能到达的祖先节点是自己 即是这棵SCC的根遍历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])遍历完出边后 若dfn[u] low[u] 记录答案SCC过程vectorintdfn,low;intinstack[N];// 节点u是否在栈中stackintstk;// 暂存为确定强连通分量的节点vectorvectorintsccs;//结果 每个元素是一个强连通分量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]){// 祖先找到了 依次弹出来vectorintcnt;while(1){intvstk.top();stk.pop();instack[v]0;cnt.push_back(v);if(vu)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 - 1step1从节点1出发踏进1, dfn[1] 1, low[1] 1 把1压入栈 stack [1]看1的儿子: 有2 dfn[2] 0 没去过递归进入2step2进入节点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]) 1low[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(nm)每个节点和每条边只被访问常数次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 这么说可能好理解点因为我写完这篇笔记第二天又看不懂我自己写的了vectorintg[N],reg[N];// 原图和反图intvis[N];// 标记数组vectorintorder;// 记录离开顺序vectorvectorintsccres;//scc的答案//dfs1记录离开顺序voiddfs1(intu){vis[u]1;for(intv:g[u]){if(!vis[v])dfs1(v);}order.push_back(u);}//dfs2找一个sccvectorintcnt;voiddfs2(intu){vis[u]1;cnt.push_back(u);for(intv:reg[u]){if(!vis[v])dfs2(v);}}signedmain(){//第一次dfsfor(inti0;in;i){if(!vis[i])dfs1(i);}//逆序遍历ordermemset(vis,0);for(intin-1;i0;i--){intuorder[i];if(!vis[u]){cnt.clear();dfs2(u);sccres.push_back(cnt);}}return0;}时间复杂度O(nm) 两次dfs, 每个节点和每条边访问常数次三.总结KosarajuTarjan思想难度低 拓补序有点高 dfn/low代码实现两次dfs反图 代码量有点多简短但复杂的一个dfs效率常数略大常数小时间复杂度O(nm)O(nm)若给的图不大 那么kosaraju最稳 若追求效率则Tarjan 但是两种其实都很好用