Low-link 值

无向版本询问的是“这棵子树有没有另一条路通向上方”。父节点不必重新检查每个后代，只需接收一个最小编号。对树边 $(u,v)$，若 $low[v]>tin[u]$，子树无法绕过这条边回到 $u$ 或其祖先，因此这条边是桥。

删顶点比删边更苛刻。若回边只能回到 $u$ 本人，删除边 $(u,v)$ 后仍可绕行，删除 $u$ 后绕行出口却一起消失。因此非根 $u$ 是割点，当且仅当存在树孩子 $v$ 满足 $low[v]\ge tin[u]$。DFS 根没有父方向可比较；它是割点，当且仅当有至少两个树孩子。

图中回传的是无向桥判据的 low 值。Tarjan SCC 保留相似的最小值操作，但栈约束用于排除已经封闭的分量，不能从图中的“返祖”直觉直接省略该条件。

取无向边 $ab,bc,ca,cd$，从 $a$ 开始按 $a,b,c,d$ 发现，编号为 $1,2,3,4$。在 $c$ 扫到非树边 $ca$ 时，$low[c]$ 从 $3$ 降为 $1$；$d$ 没有其他出口，故返回 $low[d]=4$。回溯得到 $low[b]=1$、$low[a]=1$。于是 $cd$ 满足 $4>3$，是唯一桥；$bc$ 不满足 $1>2$，不是桥。顶点 $c$ 因孩子 $d$ 满足 $4\ge 3$ 成为割点，而根 $a$ 只有一个 DFS 孩子，虽然图中有两条关联边，仍不是割点。

若只有 $u,v$ 两点，却有两条平行边，DFS 用第一条到达 $v$，第二条提供返回 $u$ 的另一条路。正确结果是 $low[v]=tin[u]$，没有桥。若按“邻点等于父顶点”跳过两条边，就会误报；必须给边编号，只跳过实际父边的反向记录。

SCC 的栈区别也有具体后果。设有向边为 $a\to b,b\to a,a\to c,c\to b$，先搜索 $b$ 再搜索 $c$。$b$ 的调用已经返回，但因能回到 $a$，它尚未从分量栈弹出。此时 $c\to b$ 仍必须降低 $low[c]$，最终三点一起出栈。反之，若先单独完成孤立点 $b$，随后搜索只有弧 $c\to b$ 的 $c$，$b$ 已出栈，这条边不能让二者合成一个分量。

桥、割点、边双连通分量和强连通分量理路强连通分量算法Strongly connected components algorithm在线性时间内把有向图划分为互相可达的极大顶点集合。都可在邻接表上借助一次 DFS 的局部回传求得，时间为 $O(|V|+|E|)$，辅助空间为 $O(|V|)$。共同点是避免对子树反复搜索；具体判据仍由各自的连通性问题决定。

若要真正输出点双连通边块理路点双连通块与边栈分解Vertex-biconnected blocks · Biconnected edge-block decomposition · 点双连通分量在无自环无向多重图的 DFS 中维护未归属边栈，在线性时间内输出以边为划分、以割点为接合处的全部点双连通块。，还需维护尚未归属的边栈：孩子返回满足 $low[v]\ge tin[u]$ 时，弹到进入该孩子的树边为止。不同块可以共享割点，每条边只归属一次；保存这条边栈及显式边块输出后，辅助空间与输出合计为 $O(|V|+|E|)$，不再只有顶点状态。

这些值依赖当前边集和本次 DFS 树。全动态连通理路全动态连通性Fully dynamic connectivity · Dynamic graph connectivity以分层生成森林和 replacement-edge 搜索维护在线边插入删除下的无向图连通性，并用边层级单调提升证明多对数摊还更新界。在边插删后维护生成森林和替代边，不能只改几个 low 值继续沿用原来的证明。支配树与 Lengauer–Tarjan 算法理路支配树与 Lengauer–Tarjan 算法Dominator tree · Lengauer–Tarjan algorithm · 支配树从全部入口路径定义支配关系，用可手算例子解释半支配点、路径最小值、延迟判定与 LT 算法的两种复杂度界。也使用 DFS 编号，但它问“所有入口路径是否必经某点”，与 low-link 记录“是否存在一条返回路线”有不同的量词和目标。