【图论】Tarjan 入门

配套 Tarjan 讲解文章：[【图论】Tarjan 入门](https://www.luogu.com.cn/article/dh3sf53l)。 本题单收录做法为 Tarjan 的较简单题目（不排除部分题目还有其他做法）。如果想要**入门 Tarjan**，本题单适合。 题目难度大致为**绿-蓝**，**提高组**选手适合（Tarjan 算法在提高组大纲中）。 部分题目可能需要以下基础： - 栈。 - `vector` 的用法。 - 基础 dp。 - 拓扑排序。 注意到 Tarjan 算法的码量有时多于 $100$ 行，所以学习本算法还要求您有较强的代码实现能力。 ## Tarjan 介绍： Tarjan 算法是一种可以在 $\operatorname{O}(n+m)$ 的时间复杂度内求解一张有向图的强连通分量的算法。 强连通分量：在一张有向图 $G$ 中，如果两个点 $u$ 和 $v$ 满足 $u$ 可到达 $v$ 且 $v$ 可到达 $u$，则称 $u$ 和 $v$ 强连通；一个强连通分量要求在该分量里的任意两个点强连通。 求出了强连通分量，就可以缩点了，把同一个强连通分量里的点缩成一个。缩完的图显然是个 DAG（如果还有环就还有强连通分量）。于是就可以在 DAG 上 dp，拓扑排序等了。同时 Tarjan 的遍历顺序还是逆拓扑序，因此可以把 dp 和 Tarjan 写在一起。不过两个算法的时间复杂度都是线性的，这么写用处不大。 Tarjan 算法也可以求解一张无向图的割点和割边。 割点：如果在一张无向图 $G$ 中去掉了点 $u$ 导致图不连通，点 $u$ 称为该图的割点。割边的定义类似，如果在一张无向图 $G$ 中去掉了边 $w$ 导致图不连通，边 $w$ 称为该图的割边。 显然割点和割边不是唯一的。Tarjan 算法也可以在 $\operatorname{O}(n+m)$ 的时间复杂度内求解一张无向图的所有割点和割边。 同时该算法也可以求解双连通分量问题，具体见 P8436 和 P8435。 ## 题目的提示： **强连通分量：B3609、P2863、P1726、P1407。** B3609：模板。 P2863：模板。 P1726：模板。 P1407：虽然是无向边，但是可以把夫妻化有向边为男->女，情侣为女->男，正确性很微妙。此外还有二分图做法。 **缩点：P3387、P10944、P2746、P2341、SP14887、P3627、P1073、P2272、P2515。** P3387：模板。 P10944：缩完点是链就符合条件。 P2746：缩完点考虑怎样加边让所有学校都有。 P2341：缩完点后，考虑什么样的点是受欢迎的。 SP14887：缩完点跑 dijstkra 或者拓扑排序。 P3627：缩完点后在 DAG 上 dp。 P1073：缩完点跑拓扑排序，拓扑排序的过程中 dp。 update 2024.10.24：P1073 的新 hack 数据参考代码也可通过。 P2272：缩完点后在 DAG 上 dp，注意删掉重边防止重复计算方案。 P2515：tarjan 和树上背包的结合体，需要先缩点然后再跑一遍树上背包。但是因为数据太小，还保证是基环树，所以可以有其他做法。 **割点：P3388、UVA315、P3469、P3225。** P3388：模板。 UVA315：模板，难点在于读入。 P3469：考虑对于不是割点和是割点分开计算。 P3225：求完割点之后，考虑每个割连通块（即 dfs 到割点就停止 dfs 的连通块）中的割点个数。 **边双连通分量：P8436、P2860、P2783、P7924。** P8436：模板。 P2860：先考虑树的情况。 P2783：缩边双（每个点只会出现在一个边双上）然后建新图跑 lca。 P7924：不难注意到一条路径上若经过 $x$，则 $x$ 所在边双所有点都会被算入答案，所以缩边双，然后跑 lca，树上差分就行了。 **点双连通分量：P8435、B3610。** P8435：模板。 B3610：块的定义就是点双，但是不包括单个点。 [口胡题解及参考代码](https://www.luogu.me/article/7cgte8ex)。马蜂比较丑，见谅。