割点与桥 (Tarjan 算法)¶

在无向连通图中：

割点 (Cut Vertex / 关节点)：若删除该顶点及其关联的所有边后，图的连通块数量增加，则该顶点为割点。
桥 (Bridge / 割边)：若删除该边后，图的连通块数量增加，则该边为桥。

Tarjan 算法能够在 \(\mathcal{O}(V + E)\) 时间内，通过一次深度优先搜索同时求解出图中的所有割点与桥。

核心定义：时间戳与追溯值¶

dfn[u]（时间戳）：节点 \(u\) 在 DFS 遍历过程中首次被访问的时间序号。
low[u]（追溯值）：节点 \(u\) 及其在 DFS 树中的子孙节点，通过至多一条不在 DFS 树上的返祖边 (Back-edge) 所能到达的节点的最小 dfn 值。

判定准则¶

桥的充要条件：对于无向边 \((u, v)\)（在搜索树中 \(u\) 为 \(v\) 的父节点），若：

\[ low[v] > dfn[u] \]

说明从 \(v\) 的子树内部无法通过返祖边回到 \(u\) 或 \(u\) 之前的祖先节点，因此删去边 \((u, v)\) 后子树 \(v\) 与 \(u\) 必断开，\((u, v)\) 即为桥。
割点的充要条件：
- 若 \(u\) 是 DFS 树的根节点：当且仅当 \(u\) 在搜索树中有 \(\ge 2\) 个子节点时，\(u\) 是割点；
- 若 \(u\) 不是 DFS 树的根节点：当且仅当 \(u\) 存在至少一个子节点 \(v\)，满足：
  
  \[ low[v] \ge dfn[u] \]
  
  说明 \(v\) 子树最多只能绕回 \(u\)，若删去 \(u\) 则 \(v\) 无法到达 \(u\) 的祖先节点，\(u\) 即为割点。

完整模版实现¶

#include <vector>
#include <algorithm>

struct TarjanCutBridge {
    struct Edge {
        int to;
        int id; // 边的编号，防止反向直接走回父节点
    };

    int n;
    std::vector<std::vector<Edge>> adj;
    std::vector<int> dfn, low;
    std::vector<bool> is_cut;
    std::vector<int> bridges; // 存储桥的边编号 id
    int timer = 0;

    TarjanCutBridge(int n) : n(n), adj(n), dfn(n, 0), low(n, 0), is_cut(n, false) {}

    void add_edge(int u, int v, int id) {
        adj[u].push_back({v, id});
        adj[v].push_back({u, id});
    }

    void dfs(int u, int edge_from) {
        dfn[u] = low[u] = ++timer;
        int children = 0;

        for (const auto &e : adj[u]) {
            int v = e.to;
            int id = e.id;
            if (id == edge_from) continue; // 不通过同一条边直接折返

            if (dfn[v]) {
                // 遇到祖先节点，更新 low[u]
                low[u] = std::min(low[u], dfn[v]);
            } else {
                children++;
                dfs(v, id);
                low[u] = std::min(low[u], low[v]);

                // 1. 判定割边 (桥)
                if (low[v] > dfn[u]) {
                    bridges.push_back(id);
                }

                // 2. 判定非根节点的割点
                if (edge_from != -1 && low[v] >= dfn[u]) {
                    is_cut[u] = true;
                }
            }
        }

        // 3. 判定根节点的割点
        if (edge_from == -1 && children >= 2) {
            is_cut[u] = true;
        }
    }

    void solve() {
        for (int i = 0; i < n; ++i) {
            if (!dfn[i]) {
                dfs(i, -1);
            }
        }
    }
};

LeetCode 经典真题精选与题解提示¶

LeetCode 1192 - 查找集群内的关键连接 (Critical Connections in a Network) 困难
提示

Tarjan 割边（桥）标准模板题。
- 题目定义“关键连接”为删除后会导致服务器无法互相访问的边，这正是图论中“桥（Bridge / 割边）”的严格定义。
- 建无向图后运行 Tarjan 算法：在 DFS 树中，当且仅当子节点 \(v\) 无法通过回退边回到祖先（即 \(low[v] > dfn[u]\)）时，边 \((u, v)\) 为关键连接。
LeetCode 1568 - 使陆地分离的最少天数 (Minimum Number of Days to Disconnect Island) 困难
提示

割点判定与网格连通性。
- 最多只需 2 天即可将任意岛屿分离（分离某个角上的陆地格最多只需消除 2 个相邻格）。因此答案只能是 0、1 或 2。
- 答案为 0：初始连通分量数量不为 1；
- 答案为 1：全图陆地数为 1，或者图中存在割点（删除该割点后图不连通）；使用 Tarjan 割点算法即可在 \(\mathcal{O}(V + E)\) 时间内高效判定；
- 其余情况答案必为 2。
LeetCode 924 - 尽量减少恶意软件传播 (Minimize Malware Spread) 困难
提示

连通分量与感染节点唯一定理。
- 通过并查集或 DFS 划分全图的连通块，并记录每个连通块的节点总数以及其中包含的初始被感染节点数量。
- 若某个连通块内恰好包含 1 个 初始感染节点，移除该节点能完全保护该连通块（获益等于连通块大小）；若连通块包含 \(\ge 2\) 个感染节点，移除任何一个都无法阻止病毒扩散，获益为 0。