有向图的连通性

强连通：如果两个点彼此都能到达对方，那么这两个点是连通的。如果一个图中任意两个点都连通，那么这个图是强连通图。

强连通分量：如果一个图不是强连通图，那么可以将其分为多个子图，使得每个子图强连通且不能与其他的子图形成强连通，那么每个子图就是强连通分量。简单点说，如果将所有子图缩成一个点，缩完后图中没有环，那么每个子图就是强连通。可以缩写为 SCC。

SCC 实际上就是一个环，然后再扩展一些点所得到的图。因此求 SCC 实质上就是找环并尽可能地扩大环。

下面介绍比较常用的 Tarjan 算法：

1 Tarjan 算法

先对图进行 DFS，形成一棵 DFS 树。DFS 树就是从根节点开始搜索，如果到达了一个没有访问过的点，那么将这条边加入树中，并标记访问。

举个例子：

该图的 DFS 树为：

我们称 DFS 树上的边为树边，通往自己祖先的边为回边，其它的边为横叉边。如上图中，\(2 \to 3\) 是树边，\(4 \to 2\) 是回边，\(5 \to 4\) 是横叉边。

回边能构成环吗？答案是肯定的。因为我可以从这个点走向祖先，然后再从祖先走向这个点。

横叉边能构成环吗？一条横叉边显然不能构成。那么有人会说了，两条呢？

我们把上面的图改一下：

这样树边 \(6 \to 7\)，横叉边 \(7 \to 5\) 与 \(5 \to 6\) 是不是就构成环了？

实际上这样是不合法的。注意这是一个 DFS 树，那么我们在搜索到 \(5\) 的时候，会遍历到 \(6\)，而不会再从 \(1\) 过去了。

那么到底能不能构成呢？答案是不能，但它有可能扩大回边所构成的环。原图中，横叉边 \(5 \to 4\) 扩大了回边 \(4 \to 2\) 所构成的环。

那么如何找环呢？

我们为每个点设置两个参数：一个是 \(num\)（大部分人喜欢称为 \(dfn\)），一个是 \(low\)。\(num_u\) 表示 \(u\) 的 DFS 序，\(low_u\) 表示从 \(u\) 出发能到达的自己的祖先中 DFS 序最小的点的 \(num\) 值。

如上图中，\(num=\{1,2,3,4,5,6\},low=\{1,2,2,2,2,6\}\)。

\(low_6=6\) 而不是 \(2\)，因为 \(2\) 不是 \(6\) 的祖先。

这时我们可以发现：所有 \(low\) 值相等的点在同一个 SCC 中，这些 SCC 中一定有一个点的 \(num\) 值等于 \(low\) 值，我们可以把这个点设为 SCC 的根。

我们可以用一个栈，每次搜到结点就将该结点入栈。在遍历完所有出边后，如果该点的 \(num\) 值等于 \(low\) 值，那么栈顶的点就都属于该 SCC，全部弹出并标记即可。

因此，只要我们算对 \(low\) 值，就能求出 SCC。

那么怎么算呢？

初始时，每个点的 \(num\) 值和 \(low\) 值相等，因为我可以从自己出发走到自己。

在遍历图时，对于边 \(u \to v\)：

• 该边是树边

那么我们应该将 \(low_u\) 与 \(low_v\) 取最小值，因为我从 \(v\) 出发能到达的祖先，我从 \(u\) 出发先到 \(v\) 的话也能到达这些祖先。

• 该边不是树边

我们也应该更新 \(low_u\)。那么应该用 \(num_v\) 更新还是 \(low_v\) 更新呢？

答案是都可以。如下图：

下图中的 DFS 树中的边为 \(1 \to 2,2 \to 3,3 \to 4\)。

我们在遍历到 \(3\) 的时候，假设我们先走的 \(3 \to 4\) 这条边，然后我们走到了 \(4\)。该点只有一个出点 \(2\)，而 \(2\) 还没搜完，它的 \(num\) 值和 \(low\) 值都为 \(2\)，但是我们可以从 \(2\) 走到 \(3\) 再走到 \(1\)，且 \(1\) 是 \(4\) 的祖先。因此不管用 \(num_u\) 还是 \(low_u\) 更新都不能算对 \(low\) 值。能正确找出所有 SCC 的前提是 \(low\) 值都算对。

但实际上我们用了一个栈，在找到根节点的时候会把所有栈顶的点都弹出。因此我们只需要保证该点的 \(num\) 值不等于 \(low\) 值而不会被判断成 SCC 的根即可。因为 \(v\) 已经遍历过了，因此 \(v\) 的 \(num\) 值一定小于 \(u\) 的 \(num\) 值，因此两种都可以。我们一般使用 \(num\) 值来更新。

这就是 Tarjan 算法的流程。下面给出例题和代码。

例题 洛谷-B3609

我们可以像链式前向星一样，把每个点所属的 SCC 编号向该点的编号加边，这样遍历每个 SCC 编号的出边就能遍历到该 SCC 的所有点了。当然，也可以使用 vector 保存每个 SCC 中的点。

代码

强连通分量的一个应用是缩点。

例题 洛谷-P3387

该题的思路为：如果我到达了一个环，那么我可以在环上逛一圈，把环上的所有点的权值都加上，然后再走到环上的任意一点离开环。于是我们可以把环缩成一个点，这个点的权值就是环上所有点的权值的和。在代码中，我们可以再建个图，加边时将原来图中所有的 \(u \to v\) 改为 \(scc_u \to scc_v\) 加边。这样新图就是一个有向无环图，我们可以使用拓扑排序 \(+\) DP。

代码