割点查找器

伪代码

一次深度优先搜索，每个结点两个数字。发现时间记录该结点第一次被看到的时刻；low-link 值记录它的子树经由一条回边所能抵达的最早结点。

dfs(u, 父结点):
    disc[u] = low[u] = ++时间
    孩子数 = 0

    对 u 的每个邻居 v:
        若 v == 父结点: 跳过
        若 v 已访问:
            low[u] = min(low[u], disc[v])   // 回边
        否则:
            孩子数++
            dfs(v, u)
            low[u] = min(low[u], low[v])
            若 父结点 != 无 且 low[v] >= disc[u]:
                标记 u 为割点

    若 父结点 == 无 且 孩子数 > 1:
        标记 u 为割点            // 根结点规则

条件 low[v] >= disc[u] 表示以孩子 v 为根的子树没有任何一条回边能爬到 u 之上。因此离开该子树的每条通路都要经过 u，删掉 u 就会把它孤立出去。根结点是特例，因为它没有可被切断的父结点：根结点恰好在拥有两个或更多 DFS 孩子时才是割点，因为那些子树只能借由它彼此相通。

分步示例演算

在一个由三角形加一条两结点尾巴构成的图上，从 A 出发执行 DFS，邻居按字母顺序选取。

示例图: 无向边 A-B、B-C、C-A 构成一个三角形，另有 C-D 与 D-E 悬挂其上。

1. 一路下探到 E. 发现时间与 low-link 在下探过程中依次赋值：A 得 1，B 得 2，C 得 3，D 得 4，E 得 5。E 是叶结点，唯一的邻居就是父结点 D，因此 low[E] 保持为 5。
2. 回到 D. low[D] = min(4, low[E] = 5) = 4。检查孩子：low[E] = 5 >= disc[D] = 4，说明 E 之下没有任何东西能越过 D。因此 D 是割点，事实上删掉 D 确实会孤立 E。
3. 回到 C. C 还有一条回边 C-A，它使 low[C] = min(3, disc[A] = 1) = 1。再并入孩子的结果为 low[C] = min(1, low[D] = 4) = 1。检查孩子 D：low[D] = 4 >= disc[C] = 3，因此 C 是割点。删掉 C 会把尾巴 D-E 从三角形上切断。
4. 回到 B. low[B] = min(2, low[C] = 1) = 1。检查孩子 C：low[C] = 1 >= disc[B] = 2 不成立，因为 C 无需经过 B 就能回到 A。所以 B 不是割点，这也符合直觉：即使没有 B，三角形依然让 A 与 C 保持连通。
5. 在根结点收尾. A 是 DFS 的根。它恰好只有一个 DFS 孩子 B，因为 C 是经由 B 而非直接抵达的。只有一个孩子意味着根结点规则不触发，因此 A 不是割点。

割点是 C 和 D。三角形 A-B-C 在 A 与 B 中没有产生割点，因为环上的每个结点都有替代通路；而在尾巴 C-D-E 上，每个内部结点都是关键的。这个对比正是核心直觉：割点存在于链上，而不在环里。

复杂度及其来源

时间: O(V + E) · 空间: O(V)

这是一次深度优先搜索，每条边只附加常数级的额外工作，因此代价与遍历本身相同。每个结点被访问一次，每条边从两个端点各被检查一次。额外状态是每个结点两个整数，即发现时间与 low-link，再加上递归栈，全都是 O(V)。朴素做法是逐个删去结点再检查连通性，代价为 O(V 乘以 (V + E))，因此 low-link 方法把一个平方级的检查压缩成了一次线性扫描。在一个有 10000 个结点、30000 条边的图上，这个差距大约是四个数量级。

何时使用关节点，何时不宜

割点、桥与双连通分量都源自同一次 DFS。具体用哪一个，取决于脆弱的是结点还是边。

常见陷阱

• 把非根规则套用到根结点上. 根结点没有父结点，因此 low[v] >= disc[u] 这条判据在那里毫无意义，通常还会把它错误地标记出来。根结点需要自己的规则：当且仅当它拥有两个或更多 DFS 孩子时才是割点。
• 在回边上使用 low[v] 而不是 disc[v]. 遇到一个已访问的结点 v 时，应当用 disc[v] 更新，而不是 low[v]。用 low[v] 可能把来自另一棵子树的值传播过来，产生偏小的 low-link，从而把真正的割点掩盖掉。
• 把孩子判据与桥的判据搞混. 割点用的是 low[v] >= disc[u]，桥用的是严格大于的 low[v] > disc[u]。仅仅一个字符之差，却是「一切都必须经过这个结点」与「一切都必须经过这条边」之间的区别。
• 按结点身份而非按边跳过父结点. 只比较父结点的标识在多重图上会出错。如果 u 与 v 之间有两条平行边，第二条其实是一条真正的替代通路，不应被跳过。请记录你是从哪条边过来的，而不只是哪个结点。
• 忘记非连通分量. 一次 DFS 只覆盖一个分量。请遍历所有结点，从每个尚未访问的结点重新发起 DFS，并为每个新的根重置根结点规则。

常见问题

什么是图中的割点？

割点又称关节点，是指删去之后会使连通分量数量增加的结点。用实际的话说，它是一个单点故障：某一对结点之间的所有通路都要经过它，因此删掉它就会把图切开。

如何找出割点？

执行一次 DFS，为每个结点记录发现时间与 low-link，即从它的子树出发、至多经由一条回边所能抵达的最早发现时间。对非根结点 u，只要存在某个 DFS 孩子 v 满足 low[v] >= disc[u]，u 就是割点。根结点则在拥有两个或更多 DFS 孩子时是割点。整个过程为 O(V + E)。

割点和桥有什么区别？

割点是删去后会让图断开的结点；桥是产生同样效果的边。两者出自同一次 DFS，差别只在一个比较：割点用 low[v] >= disc[u]，桥用严格的 low[v] > disc[u]。一个图可以有桥而没有割点，反之亦然。

为什么 DFS 的根结点是特例？

因为通用判据问的是孩子子树能否抵达当前结点之上的某处，而根结点之上什么也没有。只有当根结点把两棵或更多本来彼此分离的子树连在一起时它才是关键的，而这恰好对应「拥有两个或更多 DFS 孩子」这个条件。

割点有什么用途？

它能识别通信网络中的关键路由器、道路系统中的要害路口、故障后会使分布式基础设施分裂的服务器，以及社交网络中有影响力的中介者。可靠性工程借助它来判断在哪里投入冗余最值得。