#创作计划# Tarjan 学习笔记
2025-09-27 10:51:20
发布于：浙江
Tarjan 连通性问题学习笔记
前言
声明：跳过本部分的阅读并不影响您学习算法。
其实笔者老早一段时间就已经接触到连通一系列问题了，当时是在洛谷网校听的，老师讲的很好，就是我当堂并没有听懂。
大概是在一两周后吧，我去查了很多资料，还发帖求助过，不过越查越乱。我发现基本上每个博客甚至是教辅，都有对 Tarjan 不同的解释。就以对图边的分类来讲吧，OI-wiki 上分成了四种边，洛谷网校上分成了三种边，《算法竞赛》上分成了两种边，《信息学奥赛一本通》上甚至没有分类。类似于上述的例子还有很多。
于是我就决定先放一放。
几天前碍于 csp，决定重新学一学，通过更广的学习面，于是有了本篇博客。旨在想用蒟蒻的更好理解的语言，为大家讲清这个“庞然大物”。与其说是写给自己的学习笔记，不如说是给后人的“避坑指南”。
记录
如果您还能看到这段话，代表笔者还打算继续更新。
目前计划：更新强连通分量例题。
- upd 2025.09.24 构思好了介绍强连通分量的框架，同时手搓（手写）了一份“小博客”。
强连通分量
概念理解
- 强连通：在一个有向图 中，如果存在两个节点 是互相可达的，即从节点 开始，存在一条路径到达节点 ，则称 和 是强连通的。
- 强连通图：如果一个有向图 中，所有节点互相强连通，则称 是强连通图。
- 强连通分量（Strong Connect Component，下文直接将其称为 SCC）：对于一个有向图 ，如果 ta 不是强连通图，那么必然可以将其分为多个强连通子图（一个点构成的图也是强连通图），如果每个强连通子图都是极大的，那么我们认为这些“极大的强连通子图”即为强连通分量。
其中极大的意思是无法在扩张了，满足对于一个 SCC，不存在一个不属于该 SCC 的节点与该 SCC 中所有节点互相强连通。
以上图举例，我们认为 属于同一个 SCC，而并非两个 SCC。
算法讲解
让我们先画一个图。
为了引出算法，让我们再画一个 DFS 搜索树。
由于笔者太垃圾了，并不会对边进行上色，就将就着看吧（（（。
假设按照 的顺序进行 DFS。我们讲所有指向未被搜索的边叫做树边（如图中黑色边，且必须由父亲指向儿子），而指向已被搜索的边叫做非树边（如图中黄色边）。
好，接下来让我们直接推出一个定理。
- 不存在两个节点 和 ，满足两点不为祖孙关系，且在 和 的子树中有非树边互相连接。换句话说，如果在 的子树中有一个点由一条非树边指向 的子树的某个点，那么 的子树中就一定没有一个点由一条非树边指向 的子树的某个点。
证明：
因为两个点访问顺序必然有一个先后，当访问其中一个节点的子树时，必然会顺着那条所谓的非树边访问另外一个未被访问的节点的子树的某个节点，那么那条非树边就成了树边了，证毕。
为了方便后面的表述，我们引入一个数组 dfn，为时间戳，表示每个节点被 DFS 搜索到的顺序。
一般用代码这么实现：
void dfs(int u, int fa) {
dfn[u] = ++timestamp;
for (auto v : e[u]) {
if (v == fa) continue;
dfs(v, u);
}
}
for (int i = 1; i <= n; i++) if (!dfn[i]) dfs(i, i);
然后再定义一个 SCC 中的根为其中 dfn 最小的节点。
让我们再引出一个定理：
- 一个 SCC 中的所有点必然出现在其的根的子树中。
证明：
使用反证法。
如果一个 SCC 中的点 不在根的子树中，而是根的祖先，那么 的dfn必然小于 SCC 的根，矛盾。
如果一个 SCC 中的点 与根没有关系（指不是祖孙关系），那么想要与根强连通，必然需要来回的两条非树边，这样就违背了前面的定理。
故证毕。
至此，你已经理解了在强连通分量中，Tarjan 算法的主要应用。
那么如何判断在根的子树中那些节点属于 SCC 呢。我们需要引入一个新的数组 low，也就是通过最多一条非树边能到达的 dfn 最小的祖先的 dfn。
只要当存在一个节点 满足 ，那么它必然是 SCC 的根。
上述的定理可能会很无厘头，甚至荒谬，笔者并没有水平可以证明它（如果您有证明过程，欢迎在评论区给出），但是我可以保证你举不出反例。
或许你会觉得很晕，让我们回到最开始的图来举例吧。
在上述图中，SCC 有三个，分别为 ；其中，按照 的顺序，dfn 值分别为 ，low 值分别为 。正好符合我们的“猜测”。
让我们看看 low 的更新步骤。
- 如果节点 可以通过一条边访问一个未被访问的节点 ，那么该边为树边。我们需要先搜索节点 ，然后更新 ，因为树边并不影响我们对于“经过最多一条非树边”的限制。
- 如果节点 可以通过一条边访问自己的祖先 ，那么该边为非树边。我们更新 。注意必须得用 更新，因为已经消耗了“最多一条非树边”的限制。
- 如果节点 没有祖孙关系，那么什么也不做。
然后是回溯，我们需要再引入一个栈辅助。每个节点 在被访问时就先压栈，当其把所有边都访问完之后开始回溯。判断如果 ，那么该节点必然为 SCC 的根，我们只需一直弹栈直至弹出节点 ，中间的所有节点均为同一个 SCC。
怎么样，很神奇吧。同样的，无法证明其正确性，但是可以很轻易的证明所有不为同一个 SCC 的点 ，一定会在此之前先被弹栈。因为如果 与 不强连通，那么必然是 为一个大于 ，小于等于 的数（因为节点 是一定可以通过树边直达 的），既然时间戳比根 晚，所以就能很轻易的得出时间戳为 的节点会在 回溯之前将 弹栈。
上述推导建议自己再多举几个例子，稍微理解后再往下看，如果还有疑问，可以直接提出。
为了更加实际些，我将给出模板代码以加深印象（Tarjan 模板形式很多，建议选择一种自己最喜欢的背下来，今后就不要改了）。
#define time lsdfjld//为了避免变量名重复，先打一个乱码
/*
dfn，low：意义如上文描述，为时间戳，通过最多一条非树边能到达的最小的时间戳
st：栈
cnt：每一个 SCC 的编号 sccid：每个点属于哪一个 SCC（存储的是 cnt 的编号）
你可能在别的地方看到的都是 sccno，其实是一个东西，只是我觉得 sccid 好听点（（（
*/
void dfs(int u) {
dfn[u] = low[u] = ++time;//初始化
st.push(u);//压栈
for (auto v : e[u]) {
if (!dfn[v]) {//时间戳为0表示的是还未访问过，也就是该边为树边
dfs(v);
low[u] = min(low[u], low[v]);
} else if (!sccid[v]) low[u] = min(low[u], dfn[v]);
/* sccid为0表示还在栈中，也就是v是u的祖先节点 */
//和上文的更新一样
}
if (dfn[u] != low[u]) return;//不同的话直接返回
++cnt;//相同表示又多了一个 SCC
while (!st.empty()) {
int top = st.top();
st.pop();
sccid[top] = cnt;//存储编号
if (top == u) break;//弹到自己了就结束
}
}
有帮助，赞一个