强连通分量

定义

在有向图 \(G\) 中，如果两个顶点 \(v_i,v_j\) 间 \((v_i>v_j)\) 有一条从 \(v_i\) 到 \(v_j\) 的有向路径，同时还有一条从 \(v_j\) 到 \(v_i\) 的有向路径，则称两个顶点强连通 (strongly connected) 。

如果有向图 \(G\) 的每两个顶点都强连通，称 \(G\) 是一个强连通图。

有向图的极大强连通子图，称为强连通分量。

Kosaraju 算法（也称为 Kosaraju-Sharir 算法）是线性时间的算法来找到一个有向图的强连通分量。

这个算法利用了一个事实，即转置图（同图中的每边的方向相反）具有和原图完全一样的强连通分量。

Kosaraju 算法比较关键的部分是同时应用了原图 \(G\) 和反图 \(GT\) 。

首先，在原图 \(G\) 上第一次深搜遍历时，记录时间 i 离开的顶点 j ，即 numb[i]=j （当然，也可以记录第 j 个顶点离开的时间 i ）。

接着，每一次循环我们需要找到没有找过的顶点中具有最晚离开时间的顶点进行深搜（对于 \(GT\) 来说）。每次深搜都得到一个强连通分量。

隐藏性质:

我们注意到第二次深搜选择树的顺序有一个特点：如果把求出来的每个强连通分量收缩成一个点，并且用求出每个强连通分量的顺序来标记收缩后的节点，那么这个顺序其实就是强连通分量收缩成点后形成的有向无环图的拓扑序列。

（注：在一个有向无环图中，所有活动可排列成一个线性序列，使得每个活动的所有前驱活动都排在该活动的前面，我们把此序列叫做拓扑序列 (Topological order) 。）

实现思路：

由于算法的时间取决于两次 DFS ，因此时间复杂度，对于稀疏图是 O(V+E) ，对于稠密图是 O(V^2) ，可见这是一个线性算法。

Tarjan 算法主要需要维护以下三个信息：

一个栈，用于记录当前已经访问过但是还没有被归类到任意强连通分量的节点。
dfn[u] ，表示点 \(u\) 的 DFS 序（第一次出现的时间），即标记点 \(u\) 是第几个被 DFS 到的点（前置知识：DFS 树）。
low[u] ，从 \(u\) 或者以 \(u\) 为根的子树中的结点出发通过一条返祖边或者横叉边可以到达的时间戳最小的，且能够到达 \(u\) 的结点 \(v\) 的时间戳

low[] 的计算方法：

假设当前正在对点 \(u\) 做 DFS 且正在处理一条从 \(u\) 向 \(v\) 的边。

强连通分量的根的判定：dfn[u]==low[u] 。此时，需要将整个强连通分量从栈中弹出。

判断横叉边是否符合条件：v 在栈里。

例题：Code

注：部分资料来源于百度百科

参考资料：

【R9OI】Tarjan 算法及其应用（https://www.bilibili.com/video/BV1ya411M7Tc）