割边、边双连通分量和缩点

一、 核心建图技巧：成对变换（反边快速定位）

在包含重边的无向图中，DFS 遍历时若仅通过 v != fa 防走回头路，会导致平行重边被误判忽略。必须精确忽略到达当前点的那条具体无向边。

• 编号规则：链式前向星边序号 cnt 从 2 开始计数，每次加入一条无向边时，连续建立正反两条有向边：

• 第 1 条无向边：正边 2 $({0010}_2)$，反边 3 $({0011}_2)$。

• 第 2 条无向边：正边 4 $({0100}_2)$，反边 5 $({0101}_2)$。

• 位运算性质：有向边 e 的反向边序号必为 e ^ 1，所属原始无向边编号（从 1 开始）为 e >> 1。

二、 概念定义与 Tarjan 判定法则

1. 基础定义

• 割边（桥）：无向图中，删去某条边后连通块数量增加，则该边为割边。

• 双连通分量（Biconnected Component）：

• 边双连通分量（E-BCC / E-DCC）：无向图中，若两点 $u$ 和 $v$ 无论删去哪一条边都依然连通，则称其边双连通。极大边双连通子图称为边双连通分量（内部不含任何割边）。

• 点双连通分量（V-BCC / V-DCC）：无向图中，若两点 $u$ 和 $v$ 无论删去哪一个其他点都依然连通，则称其点双连通，对应极大子图为点双连通分量（注意与边双区分）。

• 时间戳与追溯值：

• $\text{dfn}[u]$：节点 $u$ 首次被访问的 DFS 序。

• $\text{low}[u]$：$u$ 的子树通过树边及最多一条非树边能到达的最小 $\text{dfn}$ 值。

2. 无向图 DFS 边处理（微调自强连通分量 Tarjan）

当前处于节点 $u$（由有向边 in_edge 到达），枚举出边 $e=(u,v)$：

1. 反边忽略：若 e == (in_edge ^ 1)，直接跳过。

2. 树边：若 $\text{dfn}[v]==0$，递归访问 $v$，回溯时执行 $\text{low}[u]=min(\text{low}[u],\text{low}[v])$.

3. 非树边（回边/弃边合并处理）：若 $\text{dfn}[v]\ne 0$，直接执行 $\text{low}[u]=min(\text{low}[u],\text{dfn}[v])$（若为连向子树的弃边，因 $\text{dfn}[v]>\text{dfn}[u]\ge \text{low}[u]$，不会产生错误更新）。

3. 割边与边双判定（扎口袋机制）

当节点 $u$ 的所有邻边遍历完毕回溯时，若满足：

$$\text{dfn}[u]==\text{low}[u]$$

说明 $u$ 及其子树无法连回 $u$ 的任何祖先：

• 求割边：此时 $u$ 的上方边要么不存在（$u$ 为连通块 DFS 树根），要么必为割边（即 in_edge >> 1 是割边，等价于父节点视角下的 $\text{low}[u]>\text{dfn}[fa]$）。

• 划分边双：栈中从栈顶到 $u$ 的所有节点恰好构成一个边双连通分量，弹栈打包即可。

三、 边双缩点

将每个边双视为一个超级节点（编号 $1\sim \text{ebcc\_cnt}$），利用原图中的割边连接不同超级节点。

• 缩点性质：边双缩点后，原图的每个连通区都会变成一棵树（整体为森林）。

• 天然无重边：不同边双之间至多只有一条割边相连（若有两条则会成环并合并为同一边双），因此遍历原图边并在 bel[u] != bel[v] 时连边，不会产生重边。

四、 模板（时间/空间复杂度 $O(V+E)$）

const int N = 200005, M = 1000005; // M 开至无向边数的 2 倍以上

int head[N], to[M], nxt[M], cnt = 2;
int dfn[N], low[N], tot;
int stk[N], top;
int bel[N], ebcc_cnt;
bool is_bridge[M >> 1];

vector<int> tree[N];

void add(int u, int v) {
    to[cnt] = v, nxt[cnt] = head[u], head[u] = cnt++;
}

void tarjan(int u, int in_edge) {
    dfn[u] = low[u] = ++tot;
    stk[++top] = u;
    for (int i = head[u]; i; i = nxt[i]) {
        if (i == (in_edge ^ 1)) continue;
        int v = to[i];
        if (!dfn[v]) {
            tarjan(v, i);
            low[u] = min(low[u], low[v]);
        } else {
            low[u] = min(low[u], dfn[v]);
        }
    }
    if (dfn[u] == low[u]) {
        if (in_edge) is_bridge[in_edge >> 1] = true; // 非树根则上方边必为割边
        ++ebcc_cnt;
        do {
            bel[stk[top]] = ebcc_cnt;
        } while (stk[top--] != u);
    }
}

void build_tree(int n) {
    for (int u = 1; u <= n; ++u)
        for (int i = head[u]; i; i = nxt[i])
            if (bel[u] != bel[to[i]])
                tree[bel[u]].push_back(bel[to[i]]);
}

---

割边、边双连通分量和缩点题单