Tarjan 算法总结

在阅读下列内容之前，请务必了解 图论相关概念 中的基础部分。

强连通分量

简介

强连通的定义是：有向图 G 强连通是指，G 中任意两个结点连通。

强连通分量（Strongly Connected Components，SCC）的定义是：极大的强连通子图。

这里要介绍的是如何来求强连通分量。

Tarjan 算法

引入

Robert E. Tarjan（罗伯特・塔扬，1948~），生于美国加州波莫纳，计算机科学家。

Tarjan 发明了很多算法和数据结构。不少他发明的算法都以他的名字命名，以至于有时会让人混淆几种不同的算法。比如求各种连通分量的 Tarjan 算法，求 LCA（Lowest Common Ancestor，最近公共祖先）的 Tarjan 算法。并查集、Splay、Toptree 也是 Tarjan 发明的。

我们这里要介绍的是在有向图中求强连通分量的 Tarjan 算法。

DFS 生成树

在介绍该算法之前，先来了解 DFS 生成树，我们以下面的有向图为例：

有向图的 DFS 生成树主要有 4 种边（不一定全部出现）：

1. 树边（tree edge）：示意图中以黑色边表示，每次搜索找到一个还没有访问过的结点的时候就形成了一条树边。
2. 反祖边（back edge）：示意图中以红色边表示（即 $7\to 1$），也被叫做回边，即指向祖先结点的边。
3. 横叉边（cross edge）：示意图中以蓝色边表示（即 $9\to 7$），它主要是在搜索的时候遇到了一个已经访问过的结点，但是这个结点 并不是 当前结点的祖先。
4. 前向边（forward edge）：示意图中以绿色边表示（即 $3\to 6$），它是在搜索的时候遇到子树中的结点的时候形成的。

我们考虑 DFS 生成树与强连通分量之间的关系。

如果结点 $u$ 是某个强连通分量在搜索树中遇到的第一个结点，那么这个强连通分量的其余结点肯定是在搜索树中以 $u$ 为根的子树中。结点 $u$ 被称为这个强连通分量的根。

反证法：假设有个结点 $v$ 在该强连通分量中但是不在以 $u$ 为根的子树中，那么 $u$ 到 $v$ 的路径中肯定有一条离开子树的边。但是这样的边只可能是横叉边或者反祖边，然而这两条边都要求指向的结点已经被访问过了，这就和 $v$ 不在以 $u$ 为根的子树中矛盾了。得证。

Tarjan 算法求强连通分量

Tarjan 算法基于对图进行 深度优先搜索。我们视每个连通分量为搜索树中的一棵子树，在搜索过程中，维护一个栈，每次把搜索树中尚未处理的节点加入栈中。

在 Tarjan 算法中为每个结点 $u$ 维护了以下几个变量：

1. ${\mathit{\text{dfn}}}_u$：深度优先搜索遍历时结点 $u$ 被搜索的次序。
2. ${\mathit{\text{low}}}_u$：在 $u$ 的子树中能够回溯到的最早的已经在栈中的结点。设以 $u$ 为根的子树为 ${\mathit{\text{Subtree}}}_u$。${\mathit{\text{low}}}_u$ 定义为以下结点的 $\mathit{\text{dfn}}$ 的最小值：${\mathit{\text{Subtree}}}_u$ 中的结点；从 ${\mathit{\text{Subtree}}}_u$ 通过一条不在搜索树上的边能到达的结点。

一个结点的子树内结点的 dfn 都大于该结点的 dfn。

从根开始的一条路径上的 dfn 严格递增，low 严格非降。

按照深度优先搜索算法搜索的次序对图中所有的结点进行搜索，维护每个结点的 dfn 与 low 变量，且让搜索到的结点入栈。每当找到一个强连通元素，就按照该元素包含结点数目让栈中元素出栈。在搜索过程中，对于结点 $u$ 和与其相邻的结点 $v$（$v$ 不是 $u$ 的父节点）考虑 3 种情况：

1. $v$ 未被访问：继续对 $v$ 进行深度搜索。在回溯过程中，用 ${\mathit{\text{low}}}_v$ 更新 ${\mathit{\text{low}}}_u$。因为存在从 $u$ 到 $v$ 的直接路径，所以 $v$ 能够回溯到的已经在栈中的结点，$u$ 也一定能够回溯到。
2. $v$ 被访问过，已经在栈中：根据 low 值的定义，用 ${\mathit{\text{dfn}}}_v$ 更新 ${\mathit{\text{low}}}_u$。
3. $v$ 被访问过，已不在栈中：说明 $v$ 已搜索完毕，其所在连通分量已被处理，所以不用对其做操作。

将上述算法写成伪代码：

TARJAN_SEARCH(int u)
vis[u] = true low[u] = dfn[u] =
    ++dfncnt push u to the stack for each (u, v)
        then do if v hasn't been searched then TARJAN_SEARCH(v) // 搜索
    low[u] = min(low[u], low[v])                                // 回溯
    else if v has been in the stack then low[u] = min(low[u], dfn[v])

对于一个连通分量图，我们很容易想到，在该连通图中有且仅有一个 $u$ 使得 ${\mathit{\text{dfn}}}_u={\mathit{\text{low}}}_u$。该结点一定是在深度遍历的过程中，该连通分量中第一个被访问过的结点，因为它的 dfn 和 low 值最小，不会被该连通分量中的其他结点所影响。

因此，在回溯的过程中，判定 ${\mathit{\text{dfn}}}_u={\mathit{\text{low}}}_u$ 是否成立，如果成立，则栈中 $u$ 及其上方的结点构成一个 SCC。

时间复杂度 $O(n+m)$。

分量标号和拓扑序的关系

Tarjan 算法在处理过程中，实际上是按照某种 逆拓扑序 来发现强连通分量的，这是因为算法在深度优先搜索的过程中会先访问那些没有出边的节点，而这与拓扑排序的过程是相反的。

如果我们将图中的所有强连通分量缩成单个节点，那么在这些缩点后的节点形成的 DAG 中进行拓扑排序，得到的顺序将与 Tarjan 算法给出的强连通分量的标号顺序相反。

因此，可以说，在缩点后的 DAG 中，强连通分量（缩点后）的标号顺序是其拓扑序的逆序。但要注意的是，这种说法仅在考虑了强连通分量之间的依赖关系（即从一个强连通分量到另一个强连通分量的有向边）时才成立。单个强连通分量内部的节点由于存在环，所以内部并不满足拓扑序的定义。

Tarjan 缩点

其实这也是利用了 tarjan 求强连通分量的方法，对于一些贡献具有传导性，比如友情啊、路径上的权值啊等等非常适用。

思想就是因为强连通分量中的每两个点都是强连通的，可以将一个强连通分量当做一个超级点，而点权按题意来定。

首先我们先看一下一个问题：一个有向图，有 n 个点以及 m 条边，我们至少应该添加几条边才能使整个图变成强连通图。或者是一个无向图至少添加几条边变成连通图。

首先我们对于一个有向无环的图（DAG），至少添加几条边才能使它变为强连通图？我们很容易根据有向无环图的性质得到，我们计算入度为零的点数为 a，出度为零的点数为 b，那么我们至少需要添加的边数为 $max(a,b)$ ，如果只有一个点的话，我们不需要添加任何边。

那么我们怎么把一个图转换为 DAG 呢，因为上面给出的图可能存在环，那么我们就会想到把已经组成全连通的子图转换成一个点来看，那么我们最终的图就不会包含环了。

好了，解决这类问题的思路已经想好了，下面我们来进行求解：

我们使用 Tarjan 算法求解出强连通分量之后，我们上面使用了一个 color 数组将同一个连通分量的点分配相同的数值，然后我们再次遍历一遍所有的边，如果边的两侧 u->v 不属于同一颜色，那么 u 对应颜色将会有一条边连向 v 对应的颜色。在此基础上我们可以计算缩点之后的出入度，得到 $max(a,b)$ 或者其他一些信息。

其实我们上述的强连通分量 tarjan 算法已经求出了每个点属于的 color，其实每个 color 就代表了一个最大联通集

tarjan 求割点、桥

在无向连通图中，如果将其中一个点以及所有连接该点的边去掉，图就不再连通，那么这个点就叫做割点（cut vertex 或 articulation point）。

首先选定一个根节点，从该根节点开始遍历整个图（使用 DFS）。

对于根节点，判断是不是割点很简单 —— 计算其子树数量，如果有 2 棵即以上的子树，就是割点。因为如果去掉这个点，这两棵子树就不能互相到达。（注意这里的概念，称之为子树，表示了子树互不相连，而且不连向祖先）

对于非根节点，判断是不是割点就有些麻烦了。我们维护两个数组 dfn [] 和 low []。

显然如果节点 U 的所有孩子节点可以不通过父节点 U 而访问到 U 的祖先节点，那么说明此时去掉节点 U 不影响图的连通性，U 就不是割点。

相反，如果节点 U 至少存在一个孩子顶点，必须通过父节点 U 才能访问到 U 的祖先节点，也就是如果存在一个孩子 low[v]>=dfn[u]，那么去掉节点 U 后，顶点 U 的祖先节点和孩子节点就不连通了，说明 U 是一个割点。

CAUTION

无向图一定要注意回边的存在

争议点

关于 tarjan 算法，一直有一个很大的争议，就是 low[u]=min(low[u],dfn[v]);（你可以发现这和上面求强连通分量是不一样的）

这句话，如果改成 low[u]=min(low[u],low[v]) 就会 wa 掉，但是在求强连通分量时却没有问题

根据许多大佬的观点，我想提出自己的一点看法：在求强连通分量时，如果 v 已经在栈中，那么说明 u，v 一定在同一个强连通分量中，所以到最后 low [u]=low [v] 是必然的，提前更新也不会有问题，但是在求割点时，low 的定义有了小小的变化，不再是最早能追溯到的祖先，（因为是个无向图）没有意义，应该是最早能绕到的割点，为什么用绕到，是因为是无向边，所以有另一条路可以走，如果把 dfn [v] 改掉就会上翻过头，可能翻进另一个环中，所以 wa 掉。

Tarjan 求桥同理，只是条件判断改变了一点点，详情见 割点与桥 篇。