Tarjan 求双连通分量（点双连通分量、边双连通分量）

注意：本文只针对无向图。

对于无向图，显然不能只考虑简单的连通关系，应该研究一些更强的连通关系：双连通。

前置芝士

• 点双连通分量：若一个连通分量任意两点间 都存在 至少两条不经过（除起点和终点外）相同点的路径，我们就称这个连通分量 为点双连通分量。
• 边双连通分量：同理，若一个连通分量任意两点间 都存在 至少两条不经过 相同边的路径，我们就称这个连通分量 为边双连通分量。
• Tarjan 求割点和桥

首先要明确的是，若一点（或边）对于原图是割点（或桥），对于其任意包含该点（或边）的子图，该点（或边）仍是割点（或桥）。

可以想到，在一张无向图的点双连通分量中，一个割点所连的点有且只有 $1$ 个（注意这个点必须是指定点双连通分量中的）。注意不是度数为 $1$，因为可能有重边。原因是若某割点连接了一点双连通分量中的两个点，必然有删去它后该点双连通分量不连通。反之它就不是割点。

同样的，在一张无向图的边双连通分量中，必然不包含桥。

Tarjan 求点双连通分量

算法流程

首先维护一个栈 $\mathit{stk}$，一访问点 $u$，就将 $u$ 压入 $\mathit{stk}$。

书接上回，当判断一点是割点后，我们可以从 $\mathit{stk}$ 中退点，将这些点加入新的点双中，一直退到 $v$，注意不要退出 $u$，但要在当前点双中加入 $u$。

因为上文说了，虽在一个点双中，割点连接的点只有 $1$ 个，即 $v$，但 $u$ 还可能在其他点双中，故不能退栈（或者你退完压回去也可以）。

所以注意，不同于强连通分量和接下来要说的边双，一个点可能在多个点双中。

进一步的，我们甚至可以求出删去 $u$ 后连通分量的增加个数，记为 $cut_u$。每当满足 $\mathit{low}_v\ge \mathit{dfn}_u$，$cut_u\gets cut_u+1$。因为一旦删去 $u$，$v$ 将与 $u$ 的祖先脱离联系，导致连通分量数量增加 $1$。

其他与求割点相同。

代码

暂无。

Tarjan 求边双连通分量

算法流程

还是同样的维护 $\mathit{stk}$，当判定边 $(u,v)$ 为桥后，可将 $stk$ 退到 $v$，并将退的点加入一个新的边双中。有没有发现边双比点双简单多了？是的，由于桥不能存在于边双中，故退到 $v$ 即可，没有太多可叽叽歪歪的。

其他与求桥相同。

$\texttt{Upd}$：实现中，为了避免根节点（可设为 $1$）所在的边双未被退栈，可以按以下实现：

对 $u$ 的 dfs 即将结束时，判断 $dfn_u=low_u$（可得 $(u,\mathit{fa}_u)$ 为桥），若为真，则将 $stk$ 退到 $u$ 结束。这样的实现相当于在上文的 $v$ dfs 结束时直接退栈，而不是回溯到 $u$ 的 dfs 时判断、退栈。应为根节点没有父亲。

当然你也可以依然按算法流程的实现，但要加一个超级源点 $0$ 只连接根节点，这样就能保证根节点所在边双被退栈。

代码

暂无。

完结撒花！

Tarjan 连通系列正式完结啦！（除了代码）。

以后可能还会更 LCA、LCT、splay 的文章（挖大坑）。