TARJAN 连通性问题学习笔记
可能更好的阅读体验
前言
> 声明：跳过本部分的阅读并不影响您学习算法。
其实笔者老早一段时间就已经接触到连通一系列问题了，当时是在洛谷网校听的，老师讲的很好，就是我当堂并没有听懂。
大概是在一两周后吧，我去查了很多资料，还发帖求助过，不过越查越乱。我发现基本上每个博客甚至是教辅，都有对 Tarjan 不同的解释。就以对图边的分类来讲吧，OI-wiki 上分成了四种边，洛谷网校上分成了三种边，《算法竞赛》上分成了两种边，《信息学奥赛一本通》上甚至没有分类。类似于上述的例子还有很多。
于是我就决定先放一放。
几天前碍于 csp，决定重新学一学，通过更广的学习面，于是有了本篇博客。旨在想用蒟蒻的更好理解的语言，为大家讲清这个“庞然大物”。与其说是写给自己的学习笔记，不如说是给后人的“避坑指南”。
记录
> 如果您还能看到这段话，代表笔者还打算继续更新。
> 目前计划：更新强连通分量例题。
* upd 2025.09.24 构思好了介绍强连通分量的框架，同时手搓（手写）了一份“小博客”。
强连通分量
概念理解
* 强连通：在一个有向图 GGG 中，如果存在两个节点 u,vu,vu,v 是互相可达的，即从节点 uuu 开始，存在一条路径到达节点 vvv，则称 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 模板形式很多，建议选择一种自己最喜欢的背下来，今后就不要改了）。
参考资料
《深入浅出》，《算法竞赛》，《信息学奥赛一本通》，《算法竞赛进阶指南》，OI-wiki，Link。
