lessons/课程/02-强连通与双连通/03-割点点双连通与圆方树入口.md

割点、点双连通分量与圆方树入口

本节目标

学完后，你应能判断割点（articulation point），用边栈提取点双连通分量（vertex-biconnected component, v-BCC），区分点双与边双，并理解为什么点双分量重叠于割点、需要用圆方树表达。

前置知识与课前自测

前置：无向 DFS、上一节的桥与 dfn/low。

1. low[v] >= dfn[u] 与 low[v] > dfn[u] 分别对应什么？
2. DFS 根只有一个儿子时，即使满足前式，为什么不是割点？
3. 两个点双分量能共享几个原图顶点？

自测答案

1. 前者说明子树无法绕过 $u$ 到达更早祖先，对应割点/点双边界；后者说明连 $u$ 也回不到，对应桥。 2. 删除根后唯一子树内部仍连通，没有被分成两块；根需至少两个 DFS 儿子。 3. 至多一个；若共享两个点，两块可经这两点互相形成删任一点仍连通的更大点双分量。

问题动机与步步推导

逐个删点再检查连通性需要 $O(V(V+E))$。在 DFS 树中，非根点 $u$ 是割点，当且仅当存在儿子 $v$ 使

$$ low[v]\ge dfn[u]. $$

此时 $v$ 子树不能绕过 $u$ 到达 $u$ 的祖先，删掉 $u$ 就把它隔开。根没有祖先，判据改成“DFS 树儿子至少两个”。

若还要取出点双分量，只标割点不够。每次走树边或指向祖先的返祖边时，把边编号压栈；当 low[v] >= dfn[u] 时，从栈顶弹到树边 $(u,v)$，这些边及其端点组成一个点双分量。

为什么用边栈而不是点栈？割点属于多个点双分量，不能在第一次弹出后永久删除；边却恰属于一个这样的块。

核心知识

三类概念对照

概念	删除对象	块之间怎样相交	典型缩点结构
强连通分量	有向可达	点不重叠	DAG
边双连通分量	删除一条边仍连通	点不重叠	桥树/森林
点双连通分量	删除一个点后仍保持块内连通	可共享割点	圆方树/块割树

圆方树中，原顶点作为圆点，每个点双分量新建方点，并连接方点与属于该分量的原顶点。原图连通时得到一棵树；路径问题由“必须经过哪些割点”转成树路径问题。

正确性与复杂度

对树边 $u-v$，若 low[v] < dfn[u]，子树能绕过 $u$ 回到更早祖先，不在此处封闭。若 low[v] >= dfn[u]，从该树边之后压入的边无法与更早边共同处于一个更大的点双分量，应在这里恰好弹出。每条边压栈、弹栈至多一次，总时间 $O(V+E)$，空间 $O(V+E)$。

实现指南与常见错误

• 无向边按 edge_id 跳父边；重边不能按父顶点全部跳过。
• 只把 dfn[v] < dfn[u] 的已访问边压栈，避免同一无向边压两次。
• 非连通图要从每个未访问点启动 DFS。
• 单独一个点是否算点双分量依题意而定；以边为对象的题通常只处理含边分量。
• $10^5$ 深链可能触及递归栈限制；本节第二题代码为清晰展示边栈边界采用递归，实际环境若栈较小需改显式栈。

精选例题 1：Network

来源信息与题意

• VJudge：POJ-1144 Network
• 原来源：Central Europe 1996
• 大致难度：割点入门；考点：根特判、按行读取邻接表

每组给一张连通无向电话网络，$N<100$。某交换站失效后，若除它自身外还造成其他站之间不能通信，则该站是关键点。求关键点数量。输入的每行以一个点开头，后接与它直接相连的点；单独一行 0 结束本组，$N=0$ 结束输入。

Hint 1

关键点就是割点。

Hint 2

非根用 `low[child] >= dfn[u]`；根必须有至少两个 DFS 儿子。

Hint 3

输入必须用 `getline` 按行解析，不能只靠固定个数循环。

Observations、Editorial 与证明

从任一点 DFS。对非根 $u$，若某儿子子树无法连接到 $u$ 的祖先，删 $u$ 后该子树与其余图断开；反之每个儿子都能绕到祖先，删 $u$ 后仍可汇合。根只有多个独立儿子时才会造成分裂。标记后计数即可，复杂度 $O(N+M)$。

核心伪代码与参考实现附件

DFS(u, parent_edge):
    dfn[u] = low[u] = next_time()
    for each edge u-v except parent_edge:
        if v unvisited:
            DFS(v); low[u] = min(low[u], low[v])
            if u is non-root and low[v] >= dfn[u]: mark u as cut
        else: low[u] = min(low[u], dfn[v])
    root is cut iff it has at least two DFS children

完整 GNU C++17 参考实现见附件：POJ-1144.cpp

复盘与变式

若要输出“删除该点后增加多少个连通块”，非根应统计满足判据的儿子数并结合原图连通块；不能只用一个布尔标记。

精选例题 2：Simple Cycles Edges

来源信息与题意

• VJudge：CodeForces-962F Simple Cycles Edges
• 原题：Educational Codeforces Round 42
• 难度：2400；考点：点双分量、环结构判定、边编号输出

给定可不连通的简单无向图，$1\le n\le10^5$，$0\le m\le\min(n(n-1)/2,10^5)$。求恰好属于一个简单环的边，按编号递增输出。

Hint 1

先把边按点双连通分量分组；一条边的所有简单环都局限在它所在的块。

Hint 2

一个含 $V_c$ 个点、$E_c$ 条边的点双块若 $E_c=V_c$，它就是一个简单环。

Hint 3

当 `low[v] >= dfn[u]` 时，从边栈弹出一个完整块并统计不同端点数。

Observations

1. 桥属于零个环，单独形成的二点一边块不满足 $E_c=V_c$。
2. 一个简单环有相同数量的点和边，每条边只在这个环中。
3. 点双块若比简单环多边，则存在额外耳路径；块中每条边都能参与不止一种简单环，不能入选。

Editorial 与正确性

Tarjan DFS 时维护边栈，每遇到点双边界就弹出一块。用时间戳数组统计该块不同端点数；若边数等于点数，把块中全部边加入答案。

每条简单环完全包含在一个点双分量中。若块满足 $E_c=V_c$，点双连通迫使每点度数至少 2，而度数总和为 $2E_c=2V_c$，所以每点度数恰为 2，整块就是一个简单环。若 $E_c>V_c$，点双块含额外耳结构，使其中边不可能只属于唯一简单环。故筛选充要。复杂度 $O(n+m)$。

核心伪代码与参考实现附件

during undirected Tarjan, push tree/back edge IDs on a stack
when low[child] >= dfn[parent]:
    pop through the parent-child edge to obtain one vertex-biconnected block
    vertices = distinct endpoints of popped edges
    if number_of_edges == number_of_vertices:
        add every block edge to answer
sort and output answer edge IDs

完整 GNU C++17 参考实现见附件：CodeForces-962F.cpp

复盘与变式

识别信号是“边属于多少个简单环”，它比单纯判桥更细，需要看边所在点双块的整体结构。若图允许重边，两个点两条平行边是否按题目定义构成长度 2 环必须先确认，不能直接沿用简单图结论。

扩展与联系

• 圆方树把一个割点在多个点双块中的“重叠”变成树上的多条边，适合必经点计数与路径查询。
• 边双看“边是否能绕”，点双看“顶点是否能绕”；两者的 low 判据只差等号，却对应不同删除模型。
• 若要处理动态加边后的双连通性，静态 Tarjan 不再直接适用，通常需要离线、并查集或更强的动态结构。

总结与自检

1. 非根割点、根割点的判据分别是什么？
2. 为什么点双分量用边栈提取？
3. 点双分量为什么不能像边双那样直接把原点互不重叠地缩掉？
4. Simple Cycles Edges 中 $E_c=V_c$ 为什么推出块是一个环？

课后训练建议

先对拍割点：随机删点比较剩余连通块数。再手画“两个环共一个点”和“两个环共一条边”的图，分别列出点双块。第二题卡住时按 Hint 逐级展开，复盘重点是从“恰一个环”转成“点双块的边数等于点数”。