第 112A 章　割点与桥¶

前置：强连通分量

有向图讲强连通，无向图讲割点（cut vertex）和桥（bridge）—— 「删掉哪个点 / 哪条边会让网络断开」，是网络可靠性的标准建模。

判定条件建立在 dfn 与 low 之上，那两个数组以及 DFS 生成树的四类边在强连通分量的前两节，本章直接使用。差别只在一个符号：割点用 \(\ge\)，桥用 \(>\)；根节点要特判。

概念	定义
割点	删掉它（及其所有边）后，连通块数量增加
桥	删掉这条边后，连通块数量增加

1　判定条件¶

设 DFS 生成树上 \(u\) 是 \(v\) 的父亲：

对象	条件
\(u\) 是割点（\(u\) 非根）	存在儿子 \(v\) 使 \(low[v] \ge dfn[u]\)
\(u\) 是割点（\(u\) 是根）	根在 DFS 树上有 \(\ge 2\) 个儿子
边 \((u,v)\) 是桥	\(low[v] > dfn[u]\)

记忆：

割点用 \(\ge\)：儿子最多只能回到 \(u\) 自己，回不到 \(u\) 的上面 → 拿掉 \(u\) 就断了；
桥用 \(>\)：儿子连 \(u\) 都回不到 → 只能靠这条边连着。

根节点的特判是最常见的 bug。根没有父亲，\(low[v] \ge dfn[root]\) 恒成立（\(dfn[root] = 1\) 是全局最小），所以不特判会把所有有儿子的根都判成割点。

2　另一种「割点」：DAG 上的必经点¶

有一类题目也叫「割点」，讲的却是完全不同的东西：

求 DAG 的「割点」：给出一张 \(n\) 个点的拓扑图，保证点 1 能够到达点 \(n\)。找出所有的节点 \(x\)，满足删除 \(x\) 后，点 1 不能到达点 \(n\)。\(n \le 10^5\)。

DP 求出 \(S[x]\) 和 \(T[x]\)，分别表示从点 1 到 \(x\) 的路径总数，和 \(x\) 到 \(n\) 的路径总数。所谓割点，就是每条从 1 到 \(n\) 的路径都会经过的点。那么对于割点 \(x\)，\(S[x] \cdot T[x]\) 必定等于 \(S[n]\)。每个点都试一下就好了。

这是 DAG 上的「必经点」，和无向图的割点是两回事，别混淆。它的做法是路径计数：正向 DP 一遍求 \(S\)，反向 DP 一遍求 \(T\)，然后 \(S[x] \cdot T[x] = S[n]\) 就是必经点。路径数会指数级增长，实现时要取模（用两个不同的模数降低碰撞概率）， Python 大整数虽然不会溢出，但位数爆炸后乘法会变慢，照样要取模。

3　模板：迭代版求割点与桥¶

# [片段]
def cut_and_bridge(n, start, to, eid):
    """迭代版求无向图的割点与桥。O(n + m)。

    图用 CSR 存，且必须额外给出 eid：eid[i] 是第 i 条**有向半边**对应的
    无向边编号（一条无向边的两个方向共用同一个编号）。
    ——这是正确处理**重边**的关键：跳过父边要按边编号跳，不能按点编号跳。

    返回 (is_cut, bridges)：
      is_cut[u] 为 1 表示 u 是割点；
      bridges 是桥的**无向边编号**列表。
    """
    dfn = [0] * (n + 1)                      # 0 兼作「未访问」标记
    low = [0] * (n + 1)                      # low[u]：u 子树内经至多一条返祖边能爬到的最小 dfn
    is_cut = bytearray(n + 1)
    bridges = []
    it = [0] * (n + 1)                       # 出边游标，替代递归的程序计数器
    pe = [-1] * (n + 1)                      # pe[u] = u 的父边编号；根没有父边，记 -1
    idx = 0
    for s in range(1, n + 1):
        if dfn[s]:
            continue                         # 图可能有多个连通块，每块各跑一次 DFS
        idx += 1
        dfn[s] = low[s] = idx
        it[s] = start[s]
        pe[s] = -1
        call = [s]
        root_children = 0                    # 根在 DFS 树上的儿子数，只对本轮的根 s 计数
        while call:
            u = call[-1]
            if it[u] < start[u + 1]:
                i = it[u]; it[u] += 1        # i 是半边下标，先推进游标再处理，避免死循环
                v = to[i]; e = eid[i]
                if e == pe[u]:               # ★ 按边编号跳过父边，重边不会被误跳
                    continue                 # 换成 v == 父点 的写法，平行边会被一起跳掉而错判成桥
                if dfn[v] == 0:
                    idx += 1
                    dfn[v] = low[v] = idx
                    pe[v] = e                # 记下 v 是从哪条无向边下来的
                    it[v] = start[v]
                    call.append(v)
                    if u == s:
                        root_children += 1   # 只有从根直接长出的树边才算根的儿子
                elif dfn[v] < low[u]:        # 返祖边：无向图没有横跨边，不必判「在不在栈上」
                    low[u] = dfn[v]
            else:
                call.pop()
                if call:                     # 有父亲才谈得上「u 能不能爬过父亲」
                    f = call[-1]
                    if low[u] < low[f]:      # 先把 low 回传，等价于递归返回后父亲取 min
                        low[f] = low[u]
                    if low[u] >= dfn[f] and f != s:      # 割点：>=，且父亲不是根
                        is_cut[f] = 1        # u 这一坨最高只爬到 f，删掉 f 就把 u 隔离了
                    if low[u] > dfn[f]:                  # 桥：>
                        bridges.append(pe[u])            # u 连 f 都爬不到，只能靠父边 pe[u] 连着
        if root_children >= 2:               # 根的特判：根没有父亲，low[儿子] >= dfn[根] 恒成立
            is_cut[s] = 1                    # 根只有靠「儿子数」判断：两棵子树全靠根串在一起
    return is_cut, bridges


def build_undirected_csr(n, edges):
    """无向图 CSR，附带边编号 eid。edges 是 (u, v) 列表。"""
    deg = [0] * (n + 2)                      # 无向边贡献两条半边，两端的度都要加
    for u, v in edges:
        deg[u] += 1; deg[v] += 1
    start = [0] * (n + 2)                    # 度数的前缀和 = 每个点在 to 里的起始下标
    acc = 0
    for i in range(1, n + 1):
        start[i] = acc
        acc += deg[i]
    start[n + 1] = acc                       # 哨兵位，使 start[u+1] 对 u = n 也可用
    cur = start[:]                           # 各点的下一个空位
    to = [0] * acc
    eid = [0] * acc
    for i, (u, v) in enumerate(edges):       # 一条无向边拆成两条半边，共用编号 i
        to[cur[u]] = v; eid[cur[u]] = i; cur[u] += 1
        to[cur[v]] = u; eid[cur[v]] = i; cur[v] += 1
    return start, to, eid

自测：环 \(1-2-3-1\) 接上环 \(4-5-6-4\)，中间用边 \(3-4\) 相连。割点应是 \(\{3, 4\}\)，桥应是 \(\{(3,4)\}\)——上面的模板实测输出正是如此。重边测试：\(1-2\) 有两条平行边、\(2-3\) 一条，割点只有 \(2\)，桥只有 \((2,3)\) （平行边不是桥，若按点编号跳父边就会错判）。

4　本章速查¶

要点	结论
割点（非根）	存在儿子 \(v\) 使 \(low[v] \ge dfn[u]\)
割点（根）	DFS 树上儿子数 \(\ge 2\)
桥	\(low[v] > dfn[u]\)（严格大于）
跳过父边	按边编号跳，不能按点编号（否则重边被误判成桥）
DAG 的「必经点」	路径计数 \(S[x]\cdot T[x] = S[n]\)，和割点是两回事
Python 的铁律	一律写迭代，递归 \(n \ge 10^4\) 就危险
建图	用 CSR，比 `list of list` 快 2 倍、省一半内存

数据规模 → Python 现实性
迭代版割点/桥，\(n+m \le 3\times10^5\)
迭代版割点/桥，\(n+m \le 10^6\)

dfn / low / 四类边、以及 Tarjan 强连通分量的速查条目在强连通分量章末。

第 112A 章 割点与桥¶

1 判定条件¶

2 另一种「割点」：DAG 上的必经点¶

3 模板：迭代版求割点与桥¶

4 本章速查¶

第 112A 章　割点与桥¶

1　判定条件¶

2　另一种「割点」：DAG 上的必经点¶

3　模板：迭代版求割点与桥¶

4　本章速查¶