割点与点双连通分量

一、 基本概念

• 割点：在无向图中，删去某个节点及其相连的所有边后，若图的连通分量数量增加，则该节点称为割点。
• 点双连通图：不存在割点的无向连通图。
• 点双连通分量（v-BCC）：无向图的极大点双连通子图。

二、 Tarjan 算法核心原理

1. 状态定义与边分类

Tarjan 算法通过 DFS 遍历无向图，维护以下两个核心数组：

• $dfn[u]$：节点 $u$ 的 DFS 首次访问时间戳。

• $low[u]$：节点 $u$ 及其子树通过最多一条非树边能够回溯到的最早祖先的 $dfn$ 值。

对于当前遍历边 $u\to v$，按目标节点 $v$ 的时间戳状态可分为三类：

• 树边：$dfn[v]=0$，即节点 $v$ 尚未被访问，此时递归访问 $v$。

• 回边：$dfn[v]<dfn[u]$，即节点 $v$ 是 $u$ 的祖先（含父节点），用 $dfn[v]$ 更新 $low[u]$。

• 弃边：$dfn[v]>dfn[u]$，即节点 $v$ 是 $u$ 子树中已回溯的节点，直接忽略。

2. 割点判定条件

对于树边 $u\to v$，回溯后若满足 $low[v]\ge dfn[u]$，说明以 $v$ 为根的子树无法绕过 $u$ 访问到比 $u$ 更早的祖先（即节点 $u$ 对子树 $v$ 形成封闭区域，俗称“扎口袋”）。

割点的判定按节点身份分为两类：

• 非根节点：若 $u$ 不是当前连通分量的 DFS 根节点，只要存在至少一条树边 $u\to v$ 满足 $low[v]\ge dfn[u]$，则 $u$ 是割点。

• 根节点：若 $u$ 是当前连通分量的 DFS 根节点，由于其上方无祖先，恒满足 $low[v]\ge dfn[u]$；因此当且仅当 $u$ 在搜索树上的直属儿子数量 $\ge 2$ 时，$u$ 才是割点。

实现细节：无需特判父边 $v\ne fa$。当 $v$ 通过回边访问父节点 $u$ 时，$low[v]$ 最多被更新为 $dfn[u]$，不会使 $low[v]<dfn[u]$，因此不影响 $low[v]\ge dfn[u]$ 的判定结果。

3. 回边更新规则与反例分析

处理回边 $u\to v$ 时，状态转移必须写作 $low[u]=min(low[u],dfn[v])$，严禁使用 $low[v]$。

• 图例构造：设无向图含节点 $a,b,c,d$，邻接表顺序为 $a:[b,c,d]$、$b:[a,c]$、$c:[b,a]$、$d:[a]$。

• 原理解析：

• 从 $a$ 出发沿 $a\to b\to c$ 搜索，$c$ 遇到回边 $c\to a$ 后更新 $low[c]=dfn[a]=1$，回溯至 $b$ 后 $low[b]=1$。

• 若在含割点的双环结构中，节点 $u$ 的某个子树节点通过回边访问了割点 $v$，且错误执行 $low[u]=min(low[u],low[v])$，则会利用 $v$ 早已回溯到更上层祖先的 $low[v]$ 值“穿透”割点 $v$。

• 这会导致原本被割点 $v$ 隔离的子树错误获得更小的 $low$ 值（使得 $low<dfn[v]$），从而漏判割点并破坏点双连通分量的提取边界。

三、 点双连通分量提取

1. 栈维护流程

1. 节点 $u$ 初次访问时入栈。

2. 遍历树边 $u\to v$ 并完成 dfs(v) 回溯后，若满足 $low[v]\ge dfn[u]$，则触发弹栈。

3. 不断从栈顶弹出节点直至弹出 $v$，弹出的所有节点与节点 $u$ 共同构成一个点双连通分量。

4. 注意：割点 $u$ 可同时属于多个点双连通分量，因此 $u$ 仅复制加入当前分量，本身留在栈中不弹出。

2. 孤立点边界

若连通分量仅由单个孤立点 $u$ 组成（即 $u$ 为根节点且无任何相邻边），该点自身独立构成一个点双连通分量，需单独记录。

四、 代码模板

1. 割点求解模板

#include <bits/stdc++.h>
using namespace std;

const int N = 20005;
vector<int> g[N];
int dfn[N], low[N], tot;
bool cut[N];

void tarjan(int u, bool root) {
    dfn[u] = low[u] = ++tot;
    int son = 0;
    for (int v : g[u]) {
        if (!dfn[v]) {
            son++;
            tarjan(v, false);
            low[u] = min(low[u], low[v]); 
            if (low[v] >= dfn[u] && (!root || son >= 2)) cut[u] = true;
        } else {
            low[u] = min(low[u], dfn[v]); // 弃边 dfn[v] > dfn[u] 不影响最小值
        }
    } 
}

2. 点双连通分量模板

#include <bits/stdc++.h>
using namespace std;

const int N = 500005;
vector<int> g[N], bcc[N];
int dfn[N], low[N], stk[N], tot, top, cnt;

void tarjan(int u, bool root) {
    dfn[u] = low[u] = ++tot;
    stk[++top] = u;
    if (root && g[u].empty()) {
        bcc[++cnt].push_back(u);
        return;
    }
    for (int v : g[u]) {
        if (!dfn[v]) {
            tarjan(v, false);
            low[u] = min(low[u], low[v]);
            if (low[v] >= dfn[u]) {
                cnt++;
                int x;
                do {
                    x = stk[top--];
                    bcc[cnt].push_back(x);
                } while (x != v);
                bcc[cnt].push_back(u);
            }
        } else {
            low[u] = min(low[u], dfn[v]);
        }
    }
}

五、 复杂度

• 复杂度：每个节点入栈出栈一次，每条无向边常数次访问，时间复杂度 $O(V+E)$，空间复杂度 $O(V+E)$。