8
TARJAN 强连通分量学习笔记
可能更好的阅读体验
前言
> 声明：跳过本部分的阅读并不影响您学习算法。
其实笔者老早一段时间就已经接触到连通一系列问题了，当时是在洛谷网校听的，老师讲的很好，就是我当堂并没有听懂。
大概是在一两周后吧，我去查了很多资料，还发帖求助过，不过越查越乱。我发现基本上每个博客甚至是教辅，都有对 Tarjan 不同的解释。就以对图边的分类来讲吧，OI-wiki 上分成了四种边，洛谷网校上分成了三种边，《算法竞赛》上分成了两种边，《信息学奥赛一本通》上甚至没有分类。类似于上述的例子还有很多。
于是我就决定先放一放。
几天前碍于 csp，决定重新学一学，通过更广的学习面，于是有了本篇博客。旨在想用蒟蒻的更好理解的语言，为大家讲清这个“庞然大物”。与其说是写给自己的学习笔记，不如说是给后人的“避坑指南”。
记录
> 如果您还能看到这段话，代表笔者还打算继续更新。
> 目前计划：更新边双点双（会重新写一篇博客）。
* upd 2025.09.24 构思好了介绍强连通分量的框架，同时手搓（手写）了一份“小博客”。
* upd 2025.09.27 更新完了除例题外的所有部分。
* upd 2025.09.29 写完了所有部分。
* upd 2025.10.06 发现了一处笔误。
强连通分量
概念理解
* 强连通：在一个有向图 GGG 中，如果存在两个节点 u,vu,vu,v 是互相可达的，即从节点 uuu 开始，存在一条路径到达节点 vvv，同时节点 vvv 也存在一条路径到达节点 uuu，则称 uuu 和 vvv 是强连通的。
* 强连通图：如果一个有向图 GGG 中，所有节点互相强连通，则称 GGG 是强连通图。
* 强连通分量（Strong Connect Component，下文直接将其称为 SCC）：对于一个有向图 GGG，如果 ta 不是强连通图，那么必然可以将其分为多个强连通子图（一个点构成的图也是强连通图），如果每个强连通子图都是极大的，那么我们认为这些“极大的强连通子图”即为强连通分量。
其中极大的意思是无法在扩张了，满足对于一个 SCC，不存在一个不属于该 SCC 的节点与该 SCC 中所有节点互相强连通。
以上图举例，我们认为 {a,b,c,d,e}\{a,b,c,d,e\}{a,b,c,d,e} 属于同一个 SCC，而并非两个 SCC。
算法讲解
让我们先画一个图。
为了引出算法，让我们再画一个 DFS 搜索树。
由于笔者太垃圾了，并不会对边进行上色，就将就着看吧（（（。
假设按照 {a,b,d,c,f,e}\{a,b,d,c,f,e\}{a,b,d,c,f,e} 的顺序进行 DFS。我们讲所有指向未被搜索的边叫做树边（如图中黑色边，且必须由父亲指向儿子），而指向已被搜索的边叫做非树边（如图中黄色边）。
好，接下来让我们直接推出一个定理。
* 不存在两个节点 uuu 和 vvv，满足两点不为祖孙关系，且在 uuu 和 vvv 的子树中有非树边互相连接。换句话说，如果在 uuu 的子树中有一个点由一条非树边指向 vvv 的子树的某个点，那么 vvv 的子树中就一定没有一个点由一条非树边指向 uuu 的子树的某个点。
证明：
> 因为两个点访问顺序必然有一个先后，当访问其中一个节点的子树时，必然会顺着那条所谓的非树边访问另外一个未被访问的节点的子树的某个节点，那么那条非树边就成了树边了，证毕。
为了方便后面的表述，我们引入一个数组 dfn，为时间戳，表示每个节点被 DFS 搜索到的顺序。
一般用代码这么实现：
然后再定义一个 SCC 中的根为其中 dfn 最小的节点。
让我们再引出一个定理：
* 一个 SCC 中的所有点必然出现在其的根的子树中。
证明：
> 使用反证法。
> 如果一个 SCC 中的点 xxx 不在根的子树中，而是根的祖先，那么 xxx 的 dfn 必然小于 SCC 的根，矛盾。
> 如果一个 SCC 中的点 xxx 与根没有关系（指不是祖孙关系），那么想要与根强连通，必然需要来回的两条非树边，这样就违背了前面的定理。
> 故证毕。
至此，你已经理解了在强连通分量中，Tarjan 算法的主要应用。
那么如何判断在根的子树中那些节点属于 SCC 呢。我们需要引入一个新的数组 low，也就是通过最多一条非树边能到达的 dfn 最小的祖先的 dfn。
只要当存在一个节点 xxx 满足 dfnx=lowx\text{dfn}_x=\text{low}_xdfnx =lowx ，那么它必然是 SCC 的根。
上述的定理可能会很无厘头，甚至荒谬，笔者并没有水平可以证明它（如果您有证明过程，欢迎在评论区给出），但是我可以保证你举不出反例。
或许你会觉得很晕，让我们回到最开始的图来举例吧。
在上述图中，SCC 有三个，分别为 {f},{e},{a,b,c,d}\{f\},\{e\},\{a,b,c,d\}{f},{e},{a,b,c,d}；其中，按照 {a,b,c,d,e,f}\{a,b,c,d,e,f\}{a,b,c,d,e,f} 的顺序，dfn 值分别为 {1,2,4,3,6,5}\{1,2,4,3,6,5\}{1,2,4,3,6,5}，low 值分别为 {1,1,1,1,6,5}\{1,1,1,1,6,5\}{1,1,1,1,6,5}。正好符合我们的“猜测”。
让我们看看 low 的更新步骤。
* 如果节点 uuu 可以通过一条边访问一个未被访问的节点 vvv，那么该边为树边。我们需要先搜索节点 vvv，然后更新 lowu=min{lowu,lowv}\text{low}_u=\min\{\text{low}_u,\text{low}_v\}lowu =min{lowu ,lowv }，因为树边并不影响我们对于“经过最多一条非树边”的限制。
* 如果节点 uuu 可以通过一条边访问自己的祖先 vvv，那么该边为非树边。我们更新 lowu=min{lowu,dfnv}\text{low}_u=\min\{\text{low}_u,\text{dfn}_v\}lowu =min{lowu ,dfnv }。注意必须得用 dfnv\text{dfn}_vdfnv 更新，因为已经消耗了“最多一条非树边”的限制。
*
* 如果节点 u,vu,vu,v 没有祖孙关系，那么什么也不做。
然后是回溯，我们需要再引入一个栈辅助。每个节点 xxx 在被访问时就先压栈，当其把所有边都访问完之后开始回溯。判断如果 dfnx=lowx\text{dfn}_x=\text{low}_xdfnx =lowx ，那么该节点必然为 SCC 的根，我们只需一直弹栈直至弹出节点 xxx，中间的所有节点均为同一个 SCC。
怎么样，很神奇吧。同样的，无法证明其正确性，但是可以很轻易的证明所有不为同一个 SCC 的点 vvv，一定会在此之前先被弹栈。因为如果 vvv 与 xxx 不强连通，那么必然是 lowv\text{low}_vlowv 为一个大于 dfnx\text{dfn}_xdfnx ，小于等于 dfnv\text{dfn}_vdfnv 的数（因为节点 xxx 是一定可以通过树边直达 vvv 的），既然时间戳比根 xxx 晚，所以就能很轻易的得出时间戳为 lowv\text{low}_vlowv 的节点会在 xxx 回溯之前将 vvv 弹栈。
上述推导建议自己再多举几个例子，稍微理解后再往下看，如果还有疑问，可以直接提出。
为了更加实际些，我将给出模板代码以加深印象（Tarjan 模板形式很多，建议选择一种自己最喜欢的背下来，今后就不要改了）。
例题讲解
P2863 [USACO06JAN] THE COW PROM S
传送门
一个很板很板的题，再弹栈的时候判断一下 SCC 的元素即可。
具体请见代码。
P3387【模板】缩点
传送门
首先我们要知道一个关于 SCC 的定理。
* 一个点必然可以通过若干条路径遍历完 SCC 内的所有点并回到起点。
这个很好证明，强连通嘛，过去回来。
那么一条贪心策略就呼之欲出了。
> 每到一个点，就将其 SCC 内的所有点都遍历一次。
不仅白白更新了答案，又回到了起点，稳赚不赔。
然后我们就引出了连通性中一个最常见的分支，也就是缩点。
在本题中，缩点实际上就是通过将每个 SCC 缩成一个点，将原图化简成一个 DAG（有向无环图）。
DAG 能干的事可多了，因为它可以进行拓扑排序，这样我们就可以进行 DP 了。
回到这道题中，我们可以将每个 SCC 缩成一个点，同时将权值累加，最后跑一个类似于 LIS（最长上升子序列）的 DP 即可。
P2341 [USACO03FALL / HAOI2006] 受欢迎的牛 G
传送门
"牛牛 OJ"的题还是不错的。
容易发现，“喜欢”其实就是可达罢了。同样是因为 SCC 互相可达的性质，这题依旧可以缩点。
缩完点之后，我们可以保证最多只有一个“点”满足所有点均可达。因为如果存在两个点，那么就出现环了。
但是考虑到我们找这个“点”不是很方便，可以考虑到这个“点”的另外一个性质，那就是出度为 000。同样的理由，如果出度不为 000，那么就有环了。
于是我们可以写出这个一份代码：
但是这样并不能直接 AC，我们犯了一个很容易忽视的细节，那就是出度为 000 的点不一定只有一个，因此还需要特判，当存在多个出度为 000 的点时直接输出 000。
参考资料
《深入浅出》，《算法竞赛》，《信息学奥赛一本通》，《算法竞赛进阶指南》，OI-wiki，Link。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
本文共计 994099409940 个字符，从构思开始共计花了 555 天，每天码字时间大于 111 小时，制作不易，求赞 awa。
有帮助，赞一个