专题：割点、割边与双连通分量 —— 删掉谁，图就断了

本讲定位：图论系列第十四讲，无向图连通性。上一讲用 dfn/low 处理有向图的强连通分量，本讲把同一套工具搬到无向图上，回答一个新问题：删掉哪个点、哪条边，图就断成两半？ 全讲的技术含量集中在两个符号上——割点判 low[v] >= dfn[u]，桥判 low[v] > dfn[u]，一个等号之差；以及一个陷阱——判桥必须按边的编号排除来时的边，按父结点排除会在重边上翻车。这两处我都做了实测：把 >= 写成 >，2500 组随机简单图里错 1320 组；按父结点排除的写法在简单图上一个反例都没有，但一有重边就错 766/2500——是典型的”过了样例、挂了测试点”。文中所有代码经 g++ -O2 -std=c++14 -Wall 编译，割点/桥/边双三套模板各与暴力对拍 4000～5000 组，点双用两条不变量自检 2500 组。

前置知识：第 13 讲的 dfn/low 与 Tarjan 框架（强烈建议先学 13 讲，本讲是它的第二种用法）；DFS 树的概念（第 02、13 讲）。不需要 SCC 的具体结论。

适合对象：CSP-S 复赛。第 7 节（点双连通分量）标 ⭐，第一轮可跳过；边双是主线，必须掌握。

1. 从一道题说起

P1656 炸铁路：$n$ 个城市由 $m$ 条铁路连成一个连通的无向图。只有一发炮弹，炸掉一条铁路，使某两个城市之间无法互相到达。问哪些铁路是可以炸的（按字典序输出）。

换成图论语言：哪些边满足”删掉它，图就不连通了”？ 这样的边叫割边，也叫桥（bridge）。对应地，“删掉它图就不连通”的点叫割点（cut vertex / articulation point）。

暴力很好写：枚举每条边，删掉它再 DFS 一次看连通性。

for (int i = 1; i <= m; i++) {          // 枚举删哪条边
    memset(vis, 0, sizeof(vis));
    dfs(eu[i], i);                      // 第二个参数表示"禁用第 i 条边"
    if (!vis[ev[i]]) ans.push_back(i);  // 两端不连通 -> 是桥
}

复杂度 $O(m(n+m))$。炸铁路这题 $n \le 150$，暴力足够；但 P3388 割点模板 $n \le 2 \times 10^4$、$m \le 10^5$，枚举删点的 $O(n(n+m))$ 就是 $2 \times 10^4 \times 1.2 \times 10^5 = 2.4\times 10^9$，必挂。

本讲的目标：一次 DFS，$O(n+m)$，求出所有割点和所有桥。 用的还是第 13 讲那两个数组。

2. 关键区别：无向图的 DFS 树没有横叉边

第 13 讲说过，有向图 DFS 会产生四类边，其中横叉边最麻烦，逼着我们引入栈和 instk。无向图舒服得多：

无向图的 DFS 树只有树边和返祖边两类。

为什么：假设存在一条边 $(u,v)$，$v$ 已被访问过，且 $v$ 既不是 $u$ 的祖先也不是后代。既然 $v$ 先被访问（dfn[v] < dfn[u]）而 $u$ 不在 $v$ 的子树里，说明 $v$ 的 DFS 已经整个结束了。但边 $(u,v)$ 是无向的，在处理 $v$ 的时候一定会检查这条边，那时 $u$ 尚未访问，DFS 必然顺着它走到 $u$——于是 $u$ 成了 $v$ 的后代，矛盾。$\blacksquare$

这条性质带来的直接好处是本讲不需要栈，也不需要 instk：

3. low 在无向图上的含义

dfn[u] 还是时间戳，不变。