关节点和边双连通分量 · 融合风（象牙 + Obsidian 入口）

速查

关节点（割点）：删 v 后图不再连通。桥（割边）：删 e 后图不连通。判定：非根关节点 $low[v] \geq dfn[u]$；根有 ≥2 子树；桥 $low[v] > dfn[u]$（严格大于）。

核心概念 ▾

    1 --- 2
    |   / |
    3 --- 4 --- 5
          |
          6
关节点：4（删 4 后 {5}、{6} 与 {1,2,3} 不连通）
桥：(4,5)、(4,6)

利用 DFS 树定义：dfn[v] 为 DFS 时间戳；low[v] 为 v 及子孙经回边能到达的最小 dfn。

判定条件顶点 u 是关节点当且仅当：① u 是 DFS 树根且有至少两个子树；② u 非根，存在孩子 v 使 $low[v] \geq dfn[u]$。边 (u,v)（u 为 v 父）是桥当且仅当 $low[v] > dfn[u]$（严格大于）。

low 计算：$low[u] = \min(dfn[u],\ \min\{dfn[w] \mid w\ \text{经回边可达的祖先}\},\ \min\{low[v] \mid v\ \text{是孩子}\})$

从顶点 1 开始 DFS，dfn / low 表：

关节判定：顶点 1（根）只有 1 个孩子 → 不是关节点；顶点 4：孩子 5 的 $low[5]=5 \geq dfn[4]=4$、孩子 6 的 $low[6]=6 \geq 4$ → 是关节点。桥判定：$low[5]=5 > 4$、$low[6]=6 > 4$ → (4,5)、(4,6) 是桥。

题型①找关节点 ②找桥 ③判断点 / 边双连通性 ④求双连通分量。

易错清单

什么是关节点？

删除后图不再连通的顶点，也叫割点。

非根 u 何时是关节点？

存在孩子 v 使 $low[v] \geq dfn[u]$。

桥的判定条件？

$low[v] > dfn[u]$（u 是 v 的父）。

关节点 vs 桥判定区别？

关节点用 $\geq$，桥用 $>$。low=dfn 时 u 是关节点但 (u,v) 不是桥。

从顶点 1 开始 DFS，为每个顶点打 dfn 时间戳

点「DFS 定序」依次访问 1→2→3→4→5→6；再算 low、判关节点

关节点 4（两孩子 5、6 满足 low≥dfn[4]）；桥 (4,5)、(4,6)（low>dfn[4]）。