8 割点、桥、双连通元件

现在让我们回到无向图的演算法。给一张图，要判断这张图是否为连通图相当简单：只要做一次 BFS 或 DFS 就可以了。但是，如果我们想知道当某个点坏掉、或是某条边坏掉的时候，这张图是否仍然连通，那麽问题就会变得有趣许多。

如果去掉一个点(同时失去所有其相邻的边)，就会让整张图断开的话，我们称这个点为割点 (cut-vertex)、或者称为关节点 (articulation point)。如果去掉一条边，就会让整张图断开，那麽我们称这条边为一座桥。

8.1 寻找关节点的 Tarjan 演算法

Robert Tarjan 可以说是 DFS 演算法的开疆始祖。许多与 DFS 有关的演算法都以 Tarjan 为名。包含了前一节描述的强连通元件演算法，也有一个线性版本是 Tarjan 发表的(可以参考 Tarjan 在 1972 年的论文)。以今天的关节点问题来说，Tarjan 描述了一个使用 DFS 能找到所有关节点的演算法：
第一步：首先，找出一个 DFS 树，树上每个节点都有一个深度 depth(x)。
第二步：对於每一个节点 x，计算 lowpt(x)，什麽是 lowpt(x) 呢？就是 x 这个点的所有子孙节点(包含 x 自身) 能够透过非树边 (也就是回溯边 back edges) 能够抵达的最浅深度。这一步可以在线性时间内算完。

因此，对於一个节点 x 来说，如果其所有子孙能够有一条回溯边，到得了其祖先节点，那麽 x 一定不是关节点。反之，如果这个节点某个子孙节点 c 其 lowpt(c) >= depth(x)，那麽代表拿掉 x 以後，可以将 x 的祖先与 x 的子孙分开。因此， x 在这个情形下一定是关节点。

8.2 判断图是否为双连通

如果整张图都不存在关节点，那麽我们便称这张图为双连通的。因此我们知道存在一个线性 O(V+E) 时间的演算法，判断这张图是否为双连通。

8.X 冷笑话

台北的捷运路网是否存在关节点呢？其实不存在，因为可以有双连站，因此台北捷运是双连通的，直通双连。

参考资料

https://codeforces.com/blog/entry/71146
Tarjan 最早描述 DFS 的论文：https://epubs.siam.org/doi/10.1137/0201010

今天好混QQ