强连通分量
XingnoYi
·
·
算法·理论
强连通分量
（本文参考多篇资料整合而成，部分图片取自 OIwiki 和 《深入浅出-进阶版》）。
对于一个有向图，假如点 u 和点 v 可以互相到达，则称这两点强连通。
如果这张图任意两点都强连通，则称这张图为强连通图。将一个图分为多个所有点强连通的点集，则每一个点集都是这个图的强连通分量（SCC），可以理解为极大的强连通子图。
上图中共有 4 个强联通分量，分别是 \{1,3,4\}，\{2\}，\{5\} 和 \{6\}。
注意：\{1\}，\{3,4\} 等不是强联通分量，因为还有其他点和其连通。
很多有向图问题中要求出强连通分量，用来缩点（即把强连通分量替换为一个点），来建立一个点数为强联通分量个数的新图。
当一条边的两端属于不同的强联通分量，那么在新图上该分量对应的点之间连边。缩点之后的图是一张有向无环图。如下是上图缩点后的新图。
缩点是强连通分量的一种应用。
下面我们来讲如何求强连通分量。
一、Tarjan 算法
没错，又是他，和 LCA 一样。
1. DFS 生成树：
我们可以通过 DFS 生成树来辅助解决该问题。
有向图的 DFS 生成树主要有 4 种边：
-
树边：就是生成树的主干。
-
返祖边（后向边）：指向该点的祖先结点的边（ 7 \rightarrow 1）。
-
横叉边：它主要是在搜索的时候遇到了一个已经访问过的结点，但是这个结点并不是当前结点的祖先（ 9 \rightarrow 7）。横叉边一定是编号大的点指向编号小的点（注意该性质！！）。
-
前向边：指向该点子树某一节点的非树边（ 3 \rightarrow 6）。
对于求强连通分量来说：
-
前向边 (u,v) 是没有用的，因为在生成树上存在一条由树边连接 (u,v) 的一条链。
-
碰到一条返祖边 (v,u)，对于树上 (u,v) 这条链所经过的所有点，可以合并为一个集合（即构成了强连通）。
-
由于横叉边的性质，对于横叉边 (u,v) ，令 \text{LCA}(u,v) = w，假如 w 和 v 属于同一集合（强连通分量），那么可以将树上 (w,u) 这条链经过的所有点与 v 合并为一个集合。
2. Tarjan 算法主体：
定义如下数组，还有一个栈（\text{st}）：
$\text{low}_u$：在 $u$ 的子树中能够回溯到的最早的已经在栈中的结点。
设以 $u$ 为根的子树为 $\text{Subtree}_u$。
$\text{low}_u$ 定义为：在 $\text{Subtree}_u$ 中，通过若干条非树边能够到达的最上层的节点的 $\text{dfn}$ 值。
Tarjan 算法的步骤如下：
1. 从节点 $1$ 开始，将 $1$ 节点进栈，赋 $\text{dfn[1]} = 1$，$\text{low[1]} = 1$。**之后每进入一个节点 $u$，就先将 $\text{low[u]}$ 设为 $\text{dfn[u]}$，并进栈。**
------------
2. 在图上进行 DFS，先进入第一个节点 $2$（更新两个数组）。接着继续往下，直到无法继续。
3. 到节点 $4$ 时，发现了一条**返祖（前向）边（它指向了一个已被访问且在栈内的元素）**，所以我们将 $\text{low[4]}$ 设为 $\min(\text{dfn}[2],\text{low[4]}) = 2$（**取最小是因为如果是前向边，则不需要更新**）。
------------
4. 此时无法继续往下，所以回溯。**从 $v$ 回溯到 $u$ 时，更新 $\text{low}[u] =\min(\text{low}[v],\text{low}[u])$（如果有边可以返回前面的点，则此时的 $\text{low}$ 一定比它本身小；否则，它无法到达比它上层的点，所以不变 ）。** 图中回溯到了 $3$，将 $\text{low}[3]$ 更新为 $\text{low}[4] = 2$。
5. 继续回溯至点 $2$，此时更新的 $\text{low[2]}= 2 =\text{dfn}[2]$ 。当满足这个条件时，便**找到了一个强连通分量**，此时从节点从栈顶出栈，直到将该节点也出栈为止。此时所有出栈的节点就是这个强连通分量，将这些节点并入这个强连通分量集合中。
------------
6. 继续回溯，遍历下一个子树，重复操作。
7. 对于一条横叉边，当它指向的节点在栈中时，用第 $3$ 步的更新方法；若指向的节点不在栈内，说明关于指向的节点的所有操作已全部完毕，无需操作。
**注意：由于图不一定是连通图，所以我们要进行多次 DFS，直到将所有节点都遍历完。**
以 [P2683](https://www.luogu.com.cn/problem/P2863) 为例题：
### [强联通分量（Tarjan）模板](https://www.luogu.com.cn/paste/vdc7ohen)