无向图的割点与割边 (Cut Vertices & Bridges)

基于 Tarjan 递归深度树判定，通过 $low[v] \ge dfn[u]$ 极速探测网络的物理关键节点与桥梁

📖 算法原理：DFS 搜索树与连通性破坏判定

在一张无向连通图 $G = (V, E)$ 中：

📐 Tarjan 割点与桥判定定理

基于 DFS 深度优先搜索树中顶点的 dfn[u] 和 low[u] 关系：

  • 割点判定条件：
    1. 若 $u$ 为 DFS 树的根节点，当且仅当 $u$ 有至少 2 个子树节点时，$u$ 是割点（若只有 1 个子树，去掉根后剩下子树依然是一个整体）。
    2. 若 $u$ 不为根节点，当且仅当存在一个子树节点 $v$，满足 $low[v] \ge dfn[u]$。这表示 $v$ 及其子树无法通过任何反向边回溯到 $u$ 之前的祖先节点，断开 $u$ 后其子树必被孤立，故 $u$ 为割点！
  • 桥判定条件：
    • 若存在一条树枝边 $(u, v)$ 满足 $low[v] > dfn[u]$。这表示 $v$ 及其子树完全无法回溯到 $u$ 或 $u$ 之前的节点，断开该边后 $v$ 子树彻底分离，因此该无向边是桥！
🟡 已探测的割点列表 (Cut Vertices)
暂无数据
🔴 已探测的桥 (割边) 列表 (Bridges)
暂无数据
💡 趣味交互挑战：也可直接在图上点击任何顶点或边，模拟割裂“物理炸开”后图的分裂动效！
点击"开始 Tarjan 探测"观察时间戳推导，或点击图上任意元素触发物理炸裂断裂演示！
🕸️ 无向图关键桥梁物理炸裂测试场 (Cut Vertices & Bridges Physics Playground)
int dfn[MAXN], low[MAXN], timer = 0;
bool is_cut[MAXN]; // 记录是否为割点
vector<pair<int,int>> bridges; // 记录桥边

void tarjan(int u, int p = -1) {
    dfn[u] = low[u] = ++timer;
    int children = 0;
    
    for (int v : g[u]) {
        if (v == p) continue; // 忽略直接父边
        if (!dfn[v]) {
            children++;
            tarjan(v, u);
            low[u] = min(low[u], low[v]); // 子节点回溯
            
            // 1. 非根割点判定条件
            if (p != -1 && low[v] >= dfn[u]) is_cut[u] = true;
            // 2. 桥判定条件
            if (low[v] > dfn[u]) bridges.push_back({u, v});
        } else {
            low[u] = min(low[u], dfn[v]); // 返祖边更新
        }
    }
    // 3. 根节点割点判定条件：拥有至少2棵独立子树
    if (p == -1 && children > 1) is_cut[u] = true;
}
📋 算法回溯与爆炸测试历史