【图论】Tarjan 入门

配套 Tarjan 讲解文章：【图论】Tarjan 入门。

本题单收录做法为 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：块的定义就是点双，但是不包括单个点。

口胡题解及参考代码。马蜂比较丑，见谅。