「学习笔记」Tarjan 算法总结

Tarjan 算法是由 Robert Tarjan 提出的，可以求解图中的强连通分量的算法。

Tarjan 求强连通分量

如果一个有向图是强连通图，那么它的任意一对结点都可以相互到达。一个有向图的某个极大的强连通子图称为强连通分量。不难发现所有强连通分量不会有重叠。

Tarjan 算法是用来求解图中强连通分量的算法。我们定义 $\text{dfn}(i)$ 表示 $i$ 点在 DFS 树上的 DFS 序，$\text{low}(i)$ 表示 $i$ 点向下走能够访问到的结点中 dfn 的最小值。

对于每一个结点 $u$，我们访问与它相邻的点 $v$。如果这个点没被访问过，那我们就访问这个点，并用 $\text{low}(v)$ 来更新 $\text{low}(u)$。如果这个点被访问过了，我们需要看它是否已经被算进某个强连通分量中。只有它没有被算进去，我们才可以用 $\text{dfn}(v)$ 来更新 $\text{low}(u)$。因为我们要判断某个点是否已经被算进某个强连通分量中，所以我们要维护一个 bool 类型的数组 in。当 $\text{dfn}(u) = \text{low}(u)$ 的时候，我们发现从 $u$ 出发不能访问到比 $u$ 更靠前的结点了，也就是产生了一个以 $u$ 为根的强连通分量。

在 DFS 的过程中，我们维护一个栈，每次 DFS 到一个结点，我们往栈中加入这个结点，并把这个结点的 in 设成 true。拓展完所有与该结点相邻的结点后，我们判断该结点是否为一个强连通分量的根。如果是的话，该强连通分量一定是栈顶开始的一个前缀。于是我们暴力弹栈，然后将元素的 in 设为 false 即可。

下面的代码对应的题目是「BZOJ 2438」杀人游戏。这里是本题的题解。

#include <cstdio>

Tarjan 求割点

在一张无向图上，一个结点是割点，当且仅当删除掉这个结点以及与之相邻的所有边后，图变得不再联通。

Tarjan 算法可以推广到无向图上来求割点。我们进行 DFS，按照有向图上 Tarjan 的方法求出 dfn 数组和 low 数组。这里 low 数组的定义稍有改变，$\text{low}(i)$ 表示点 $i$ 不经过它的父亲结点，能够绕到的结点最小 dfn。为了方便起见，对于每条边 $(u, v)$，我们会将 $\text{low}(v) \leftarrow \min { \text{low}(v), \text{dfn}(u) }$。那么如果一个非根的结点 $u$ 是割点，那么一定存在 $\text{low(v)} = \text{dfn}(u)$。注意特判根结点是否是割点，如果是它在 DFS 树上就一定有大于等于 $2$ 个孩子。

注意我们在找到访问过的点的时候，它是一定在当前结点到根的路径上的，所以我们不需要维护 in 数组。并且因为我们最后会进行 $\text{low}(v) \leftarrow \min { \text{low}(v), \text{dfn}(u) }$ 的操作，那么我们在如果访问到了一个访问过的结点那么就不用特判它是否为原结点的父亲了，我们就可以直接来用 $\text{dfn}(v)$ 来更新 $\text{low}(u)$。

下面代码对应的题目是：「模版」割点（Luogu 3388）。

#include <cstdio>

Tarjan 求桥

桥是无向图上的某条边，满足删去这条边以后图变得不联通。

桥的求法和割点类似，我们有相同的 dfn 数组和 low 数组的定义。只是我们不再有 “为了方便起见” 对定义的略微修改。那么，如果一个结点到它的父亲的那条边是桥，那么有 $\text{dfn}(u) = \text{low}(u)$。和求割点类似，我们也不需要维护 in 数组。但是如果需要缩点的话我们还是需要维护一个栈。

求桥的难点在于处理重边。对于每一个结点，我们要记录到达每个结点的边的编号 $\text{id}(u)$。在找到一个访问过的结点的时候，我们就要判断到达该结点的边是否是 $\text{id}(u)$。如果不是的话，才使用 $\text{dfn}(v)$ 来更新 $\text{low}(u)$。

下面代码对应的题目是：「BZOJ 1718」Redundant Paths。这里是本题的题解。

#include <cstdio>