CC++ & Algorithm

割点与割边（桥）

较难2
语言版本：C++
概述：割点和割边就像网络中的关键节点和关键线路，它们一断，网络就裂开了。

割点与割边：网络里的“关键咽喉”

想象一下，你和小伙伴们玩一个“传纸条”游戏，每个人之间用绳子连起来。如果某个人被拿走，纸条就再也传不到另一边了，这个人就是割点；如果某根绳子被剪断，两边就彻底分开了，这根绳子就是割边（桥）。

割点和割边是图论里非常重要的概念，它们就像网络里的咽喉要道——一个关键路由器坏了，整个小区上不了网；一座桥塌了，河两岸的村庄就断了联系。理解它们，能帮你分析哪些地方最脆弱，需要重点保护。

1. 什么是割点和割边？

在一个连通的无向图（比如一个班级里，每个同学都能通过熟人找到另一个同学）里：

  • 割点：如果去掉某个顶点（及其相连的边），图变得不连通了，这个顶点就叫割点。
  • 割边：如果去掉某条边，图变得不连通了，这条边就叫割边（也叫“桥”）。

生活中的例子

  • 你家小区到学校只有一条主干道，这条路如果堵死了，你就没法上学了——这条路就是“桥”。
  • 学校里的网络中心，一旦断电，整个学校的网络都瘫痪——这个网络中心就是“割点”。

注意：割点不一定只能有一个。比如一个“8”字形网络，中间那个交叉点就是割点；一条直线上的所有中间点都是割点，但只有两端不是。

2. 怎么找出它们？——用DFS + 两个关键数字

要想找出割点和割边，需要用深度优先搜索（DFS）给每个顶点打上两个“印章”：

  • dfn[u]：发现时间，即DFS时第一次访问到顶点u的顺序（第几个被访问的）。
  • low[u]：回溯值，表示u在不经过它的父顶点（DFS树上的父亲）的情况下，能通过非父子边（也叫回边/返祖边）到达的最早祖先的dfn值。简单说，就是“u有秘密通道能绕到多早的祖先”。

核心规律就两条：

  1. 割点的判断：对于顶点u（除了根节点），如果存在一个孩子v，使得 low[v] >= dfn[u]，那么u是割点。
    为什么？因为low[v] >= dfn[u]说明v和它下面的子孙，最多只能回到u，无法“绕”到u之上，所以u一断，v就彻底和上面断了。

  2. 割边的判断：对于边(u,v)，如果 low[v] > dfn[u]，那么边(u,v)是割边。
    为什么？因为low[v] > dfn[u]说明v和它下面的子孙，连u都回不去（更别说上面了），所以这条边一断，v的子树就独立了。

特殊情况：根节点（DFS起点）没有父节点，它的割点判断要用另一条规则——如果根节点有至少两个孩子（在DFS树上），那么它就是割点。因为去掉根，这几个孩子之间无法连通。

3. 一步一步动手找：图解例子

假设我们有一个像这样的图（顶点0到4，边如下）：

  • 0-1, 1-2, 2-0（形成一个三角形）
  • 1-3, 3-4（一条链）

从0开始DFS：

  • 访问0（dfn=1, low=1），然后去1。
  • 访问1（dfn=2, low=2），然后去2。
  • 访问2（dfn=3, low=3），发现2的邻居有1（是父节点，跳过），还有0（不是父节点，且0已被访问，这是回边）。于是更新low[2] = min(low[2], dfn[0]) = min(3, 1) = 1。
  • 回溯到1，更新low[1] = min(low[1], low[2]) = min(2, 1) = 1。
  • 再从1去3（孩子），访问3（dfn=4, low=4），再去4。
  • 访问4（dfn=5, low=5），回溯到3，更新low[3] = min(low[3], low[4]) = min(4, 5) = 4。
  • 此时检查边(1,3)：low[3]=4，dfn[1]=2，因为4 > 2，满足low[v] > dfn[u]，所以边(1,3)是割边。
  • 再检查顶点1（非根）：孩子2的low[2]=1，dfn[1]=2，因为1 < 2，不满足low[v] >= dfn[u]，所以1不是割点；孩子3的low[3]=4 >= 2，所以1是割点？等一下，我们有一个孩子满足条件就标记为割点。因为孩子3满足low[3] >= dfn[1]（4>=2），所以顶点1是割点。
  • 根节点0：有孩子1和2（实际上2是1的孩子，但根的孩子只有1一个？注意DFS树：0只有1一个直接孩子，因为2是通过1到达的，所以根的孩子数=1，小于2，因此根不是割点。

最终结果：割点是1，割边是(1,3)。

4. 新手最容易犯的错误

  1. 忘记根节点的特殊处理：根节点只有两个及以上孩子才是割点，不能用low[v] >= dfn[u]判断，否则所有根节点都会被误判为割点（因为u是根，dfn最小，low[v] >= dfn[根]几乎总是成立）。

  2. 在回边判断时混淆：当遇到已经访问过的邻居v（且v不是父节点）时，应该用low[u] = min(low[u], dfn[v])，而不是low[u] = min(low[u], low[v])。为什么？因为回边只能让你“跳”到那个祖先的发现时间，而不能通过它再往下走（low[v]可能已经包含了更早的祖先，但那是通过另外的路径，不符合“不经过父节点”的限制）。初学者常写错成low[v]，导致low值偏低，判断出错。

  3. 割边条件写为 >= 而不是 >：割边是严格大于（low[v] > dfn[u]），如果low[v] == dfn[u]，说明v能回到u，但不等于能回到u之上，此时去掉边(u,v)，v还能通过其他路径连到u（当然其他路径不能经过u-v边本身），所以不是桥。常见的错误写成 >=。

  4. 无向图要双向添加邻接表：代码里必须adj[u].push_back(v); adj[v].push_back(u);，否则DFS时找不到反向边，会被当成新顶点。

5. 完整代码示例（带中文注释）

下面是一个完整的C++程序，读入一个图，输出所有割点和割边。代码中的变量名简短，每行都有中文注释。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int MAXN = 100;          // 最大顶点数
vector<int> adj[MAXN];         // 邻接表
int dfn[MAXN] = {0};           // 发现时间（0表示未访问）
int low[MAXN];                 // 回溯值
int dfs_clock = 0;             // 时间戳
bool isCut[MAXN] = {false};    // 是否为割点
vector<pair<int,int>> bridges; // 割边列表

void dfs(int u, int parent) {
    low[u] = dfn[u] = ++dfs_clock;  // 初始化发现时间和low值
    int childCount = 0;             // 记录DFS树中孩子个数（用于根节点判断）

    for (int v : adj[u]) {          // 遍历u的所有邻居v
        if (!dfn[v]) {              // v还没被访问过
            childCount++;
            dfs(v, u);              // 递归访问孩子
            low[u] = min(low[u], low[v]);  // 用孩子的low值更新自己

            // ----- 判断割点（非根节点）-----
            if (parent != -1 && low[v] >= dfn[u]) {
                isCut[u] = true;
            }

            // ----- 判断割边 -----
            if (low[v] > dfn[u]) {
                bridges.push_back({u, v});  // 记录割边
            }
        } else if (v != parent) {   // v已被访问且不是父节点，说明是回边
            low[u] = min(low[u], dfn[v]);   // 注意用dfn[v]而不是low[v]
        }
    }

    // ----- 根节点割点判断 -----
    if (parent == -1 && childCount >= 2) {
        isCut[u] = true;
    }
}

int main() {
    int n = 5;    // 顶点数
    // 添加无向边（双向添加）
    adj[0].push_back(1); adj[1].push_back(0);
    adj[1].push_back(2); adj[2].push_back(1);
    adj[2].push_back(0); adj[0].push_back(2);  // 0-1-2三角形
    adj[1].push_back(3); adj[3].push_back(1);  // 1-3
    adj[3].push_back(4); adj[4].push_back(3);  // 3-4

    // 对每个未访问顶点执行DFS（图可能不连通）
    for (int i = 0; i < n; ++i) {
        if (!dfn[i]) dfs(i, -1);
    }

    // 输出结果
    cout << "割点: ";
    for (int i = 0; i < n; ++i) if (isCut[i]) cout << i << " ";
    cout << "\n割边: ";
    for (auto& p : bridges) cout << "(" << p.first << "," << p.second << ") ";
    cout << "\n";

    return 0;
}

运行结果：

割点: 1 
割边: (1,3)

解释：顶点1是割点（去掉它，图分成三块：0-2一块，3-4一块，以及单独的？实际上0-2一块，3-4一块，所以不连通）。边(1,3)是割边（去掉它，子图3-4与其余部分分离）。

你可以自己修改main函数中的边，测试不同的图，看看结果是否正确。

6. 相关知识点

掌握了割点和割边，你还可以继续学习：

  • 关节点（articulation point）：和割点是一回事。
  • 双连通分量（Biconnected Component）：没有割点的极大子图叫作“点双连通分量”，没有割边的极大子图叫作“边双连通分量”。它们可以帮我们分析图的冗余程度。
  • 强连通分量（SCC）：针对有向图，用Tarjan算法也能找出环和关键点。
  • 网络流：在网络中，割边（桥）常常对应最小割，是最大流理论的基础。

试试动手画几个图，用手算一遍，再用代码验证，很快就能理解这些“咽喉要道”的秘密！

例题精讲

1单选题

在一个无向连通图中，若删除顶点v后图不再连通，则称v为割点。以下哪种说法是正确的？

A割点至少出现在两个不同的连通分量中
B割点一定是图中度数最大的顶点
C删除割点后，图的连通分量数一定增加
D割点一定是环上的顶点
2判断题

在无向图中，一条边是桥当且仅当它不在任何环中。

3填空题
下面是Tarjan算法求无向图割点的部分代码，请补充横线处的判断条件，使得算法正确（假设当前顶点u不是根节点）。
void dfs(int u, int parent) {
    dfn[u] = low[u] = ++timer;
    for (int v : adj[u]) {
        if (v == parent) continue;
        if (!dfn[v]) {
            dfs(v, u);
            low[u] = min(low[u], low[v]);
            if ( ___(1)___ ) { // 判断割点条件
                // u是割点
            }
        } else {
            low[u] = min(low[u], dfn[v]);
        }
    }
}
4单选题

在使用Tarjan算法求无向图桥时，对于一条树边(u,v)（v是u的子节点），判断该边是桥的条件是以下哪个？

Alow[v] < dfn[u]
Blow[v] > dfn[u]
Clow[v] <= dfn[u]
Dlow[v] == dfn[u]
5判断题

在一个无向连通图中，如果存在割点，则一定存在桥。