1 点双
图的割点 判断哪些点被删除后会使图分裂。现在继续求出这些分界点两侧的完整结构。
本篇采用 luogu P8435: 【模板】点双连通分量 的约定:没有割点的极大连通子图称为点双连通分量,简称点双或 v-BCC。极大表示不能继续扩大,不是只取规模最大的部分。
需要明确小规模情形:
- 一条桥与它的两个端点,单独形成一个两点分量。
- 孤立点单独形成一个单点分量。
- 自环不改变这里的顶点分块,读入时忽略;只有自环的点按孤立点处理。
当分量至少有三个顶点时,也可以用“两点之间存在两条内部顶点互不重合的路径”理解。不能把这个表述不加区分地用于上述两点、单点情形。
与 边双连通分量 不同,割点可以属于多个点双,不能给每个顶点只记一个所属编号。本篇用 block[c] 保存第
2 示例
两个三角形共用顶点
按后面的 DFS 顺序,分量依次输出为
顶点
除自环外,每条原图边恰好属于一个点双;共享的是割点,不是边。不同点双最多共用一个顶点:若共用至少两个点,删除其中任意一个点后仍能通过另一个公共点连接,两块就可以继续合并,与极大性矛盾。
3 分界条件
对 DFS 树边
说明
有等号也要出块:回到
这里不是把整个
样例中,先处理桥
4 边栈
4.1 入栈
维护 edge_stack,保存已经访问、尚未归属到某个点双的边。
每条无向边只入栈一次:
- 树边:递归进入孩子之前入栈。
- 回边:仅从后代看向祖先时入栈,即
dfn[v] < dfn[u]。 - 沿父边反向返回:跳过。
- 从祖先再次看到已经处理过的后代:不重复入栈。
同一无向边的两条邻接表记录共用一个边号。过滤的是进入边的编号,不能过滤所有通向父亲的边,否则会漏掉平行边提供的回边。
4.2 出块
当树边 low[v] >= dfn[u],不断弹出边,直到把这条树边也弹出。所有弹出边的端点,组成当前点双。
void make_block(int stop_edge) {
++bcc_count;
while (true) {
int id = edge_stack[--edge_top];
add_vertex(eu[id]);
add_vertex(ev[id]);
if (id == stop_edge) break;
}
}
停止边必须包含在块内,不能在弹出它之前结束。
4.3 顶点去重
一个顶点可能是多条弹出边的端点,在同一块内只应出现一次。用当前分量编号作为时间戳:
void add_vertex(int u) {
if (mark[u] == bcc_count) return;
mark[u] = bcc_count;
block[bcc_count].push_back(u);
}
不能用永久的 visited[u] 阻止重复加入,因为割点还要进入其他分量。每生成新块,bcc_count 改变,旧标记不会阻止它再次加入。
边栈法也不意味着点栈法不可行。点栈法需要弹到孩子
5 手算过程
按输入边顺序 DFS,访问次序为
| 边号 | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| 原边 |
到达
接下来的关键返回:
| 返回 | 判断 | 弹出边号 | 分量 |
|---|---|---|---|
| 不弹 | — | ||
| 不弹 | — | ||
弹出
顶点
6 根节点
根是否为割点,与是否生成点双,是两个判断:
| 判断对象 | 根节点规则 |
|---|---|
| 是否为割点 | DFS 孩子数至少为 |
| 是否出块 | 每个满足 low[v] >= dfn[u] 的树孩子都要出块 |
根只有一个 DFS 孩子时,不是割点,但仍要输出包含根的那个分量。
因此代码中这两个判断分开写:
if (low[v] >= dfn[u]) {
if (in_edge != -1) cut[u] = true;
make_block(id); // 不限制 u 必须是非根
}
// 完成根的全部邻边后,再按孩子数判断根是否为割点。
若把整个出块过程放进“非根才执行”的分支,会漏掉每个原连通分量最上方的点双。
7 正确性
DFS 中的树边和指向祖先的回边分别只入栈一次,每次出块只弹出一个连续栈段,因此不同点双不会重复占有同一条边。
按返回顺序考虑一次 low[v] >= dfn[u]:
- 更深处遇到的分界已经先出块,保留的栈段不包含那些已经分离的部分。
- 若保留部分中仍有一个内部割点,更深处的相应孩子返回时就应先触发出块,与它仍留在本段矛盾。
- 顶端
连接的只是当前这一支尚未封闭的部分;删去 后,这一支仍由 DFS 树相连,所以 在当前块内也不是割点。 - 当前部分不能绕过
接入上方,其他已经分离的部分也必须经过各自边界,故不能继续扩大。
因此取出的块没有内部割点且已经极大。桥以两点块处理,孤立点补单点块,覆盖全部顶点。根的每个孩子返回时同样执行出块,保证每个原连通分量中的非自环边最终全部归属。
8 代码
采用 luogu P8435: 【模板】点双连通分量 的输入输出格式。先输入
#include <bits/stdc++.h>
using namespace std;
const int maxn = 500000 + 5;
const int maxm = 2000000 + 5;
struct Edge {
int to, id;
};
vector<Edge> g[maxn];
vector<int> block[maxn];
int eu[maxm], ev[maxm];
int dfn[maxn], low[maxn], mark[maxn], edge_stack[maxm];
bool cut[maxn];
int timer = 0, bcc_count = 0, edge_top = 0;
void add_vertex(int u) {
if (mark[u] == bcc_count) return;
mark[u] = bcc_count; // 只在当前分量内去重,割点可以加入其他分量
block[bcc_count].push_back(u);
}
void make_block(int stop_edge) {
++bcc_count;
while (true) {
int id = edge_stack[--edge_top];
add_vertex(eu[id]);
add_vertex(ev[id]);
if (id == stop_edge) break; // 必须包含触发出块的树边
}
}
void dfs(int u, int in_edge) {
dfn[u] = low[u] = ++timer;
int children = 0;
for (auto [v, id] : g[u]) {
if (id == in_edge) continue;
if (!dfn[v]) {
++children;
edge_stack[edge_top++] = id; // 树边在进入孩子前入栈
dfs(v, id);
low[u] = min(low[u], low[v]);
if (low[v] >= dfn[u]) {
if (in_edge != -1) cut[u] = true;
make_block(id); // 根也要执行出块,不能加“非根”限制
}
} else if (dfn[v] < dfn[u]) {
edge_stack[edge_top++] = id; // 回边只从后代看向祖先时入栈一次
low[u] = min(low[u], dfn[v]);
}
}
if (in_edge == -1) cut[u] = (children >= 2);
}
void solve(int n) {
for (int u = 1; u <= n; ++u) {
if (dfn[u]) continue;
dfs(u, -1);
if (g[u].empty()) {
++bcc_count;
add_vertex(u); // 忽略自环后没有邻边的点,单独成块
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
for (int id = 0; id < m; ++id) {
cin >> eu[id] >> ev[id];
if (eu[id] == ev[id]) continue; // 自环不改变本题采用的顶点分块
g[eu[id]].push_back({ev[id], id});
g[ev[id]].push_back({eu[id], id});
}
solve(n);
cout << bcc_count << '\n';
for (int c = 1; c <= bcc_count; ++c) {
cout << block[c].size();
for (int u : block[c]) cout << ' ' << u;
cout << '\n';
}
return 0;
}
成员按照弹边时遇到端点的顺序收集,不需要排序。原题允许任意顺序。
输入:
7 7
1 2
2 3
3 1
3 4
4 5
5 3
5 6
输出:
4
2 5 6
3 5 3 4
3 3 1 2
1 7
其中 3 5 3 4 表示三个顶点
8.1 非递归版本
递归深度最坏达到
非递归完整代码
#include <bits/stdc++.h>
using namespace std;
const int maxn = 500000 + 5;
const int maxm = 2000000 + 5;
struct Edge {
int to, id;
};
vector<Edge> g[maxn];
vector<int> block[maxn];
int eu[maxm], ev[maxm];
int dfn[maxn], low[maxn], mark[maxn], edge_stack[maxm];
bool cut[maxn];
int timer = 0, bcc_count = 0, edge_top = 0;
void add_vertex(int u) {
if (mark[u] == bcc_count) return;
mark[u] = bcc_count; // 只在当前分量内去重,割点可以加入其他分量
block[bcc_count].push_back(u);
}
void make_block(int stop_edge) {
++bcc_count;
while (true) {
int id = edge_stack[--edge_top];
add_vertex(eu[id]);
add_vertex(ev[id]);
if (id == stop_edge) break; // 必须包含触发出块的树边
}
}
int parent[maxn], parent_edge[maxn], next_edge[maxn];
int child_count[maxn], dfs_stack[maxn];
// DFS 栈与分量边栈分开:退出孩子时,才更新 low 并检查出块。
void dfs(int root, int in_edge) {
int top = 0;
parent[root] = 0;
parent_edge[root] = in_edge;
next_edge[root] = child_count[root] = 0;
dfn[root] = low[root] = ++timer;
dfs_stack[top++] = root;
while (top) {
int u = dfs_stack[top - 1];
if (next_edge[u] == (int)g[u].size()) {
--top;
int p = parent[u];
if (p == 0) {
cut[u] = (child_count[u] >= 2);
} else {
low[p] = min(low[p], low[u]);
if (low[u] >= dfn[p]) {
if (parent[p] != 0) cut[p] = true;
make_block(parent_edge[u]);
}
}
continue;
}
auto [v, id] = g[u][next_edge[u]++];
if (id == parent_edge[u]) continue;
if (!dfn[v]) {
++child_count[u];
edge_stack[edge_top++] = id;
parent[v] = u;
parent_edge[v] = id;
next_edge[v] = child_count[v] = 0;
dfn[v] = low[v] = ++timer;
dfs_stack[top++] = v;
} else if (dfn[v] < dfn[u]) {
edge_stack[edge_top++] = id;
low[u] = min(low[u], dfn[v]);
}
}
}
void solve(int n) {
for (int u = 1; u <= n; ++u) {
if (dfn[u]) continue;
dfs(u, -1);
if (g[u].empty()) {
++bcc_count;
add_vertex(u); // 忽略自环后没有邻边的点,单独成块
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
for (int id = 0; id < m; ++id) {
cin >> eu[id] >> ev[id];
if (eu[id] == ev[id]) continue; // 自环不改变本题采用的顶点分块
g[eu[id]].push_back({ev[id], id});
g[ev[id]].push_back({eu[id], id});
}
solve(n);
cout << bcc_count << '\n';
for (int c = 1; c <= bcc_count; ++c) {
cout << block[c].size();
for (int u : block[c]) cout << ' ' << u;
cout << '\n';
}
return 0;
}
这里有两个栈:dfs_stack 模拟递归调用,edge_stack 保存尚未归属的边。只有模拟“从孩子返回”时,才更新父亲的 low 并判断出块,不能把 DFS 栈与分量边栈混用。
两版采用相同的边栈规则、时间戳去重和输出顺序。cut[u] 同时保留割点判定结果,不额外输出。
9 关联森林
点双相互重叠,不能像边双一样,把每块直接缩成互不相交的新点。
可以保留所有原顶点,再为每个点双增加一个辅助点:原顶点画圆,分量点画方。若顶点属于某分量,就在对应圆点、方点之间连边。
若分量数为
for (int c = 1; c <= bcc_count; ++c) {
for (int u : block[c]) {
tree[u].push_back(n + c);
tree[n + c].push_back(u);
}
}
tree 需另外声明为 vector<int> tree[maxn * 2]。这段是后续建图接口,模板题只输出分量,不需要执行它。
这就是圆方树的一种表示。若出现交替经过圆点、方点的环,环上的多个块就能通过另一侧绕过公共点,应当合并,与各块极大矛盾。因此原图连通时得到树,不连通时得到森林。
样例中两个割点
这层表示可以继续处理“哪些割点是必经点”等树上问题。本篇先建立结构,不展开圆方树上的路径与计数算法。
10 复杂度与边界
每条非自环边入栈、出栈各一次,端点用时间戳去重,每次只需
每个非单点分量都对应一次树孩子返回,数量不超过 DFS 树边数;再加孤立点后,分量总数不超过 block[maxn] 足够。
- 模板容量为
、 ,边栈容量按边数,显式 DFS 栈容量按点数。 - 重边必须按边号区分。另一条通向父亲的边可以作为回边入栈,不能一起跳过。
- 自环忽略后,只有自环的顶点也要输出单点分量;自环依附于其他块时,不额外生成单点块。
- 根是否为割点需要特判,根是否出块不需要取消或延后。
- 点双不允许用唯一的
belong[u]保存顶点归属,low[u]也不是分量编号。 - 不能只删去全部割点,再给剩余连通块补相邻割点。例如路径
,这种做法会漏掉由两个割点组成的块 。 - 同一顶点属于至少两个点双,当且仅当它是割点;可以用这个性质核对
cut与输出结果。 - 多组数据须清空邻接表与分量表,重置时间戳、计时器、栈顶和全部状态数组。
11 练习
11.1 手算
- 路径
有几个点双?哪些点重复出现? - 三角形从
开始 DFS,根只有一个树孩子,是否应该出块? - 输入只有顶点
和自环 ,应输出几个分量?若再增加边 呢?
参考结果
- 三个:
、 、 。割点 各出现两次。 - 应该输出整个三角形。根不是割点,不影响出块。
- 先得到单点块
;增加边后只有两点块 ,自环不会使 另成一块。
11.2 推荐题目
| 层次 | 题目 | 训练内容 |
|---|---|---|
| 模板 | luogu P8435: 【模板】点双连通分量 | 边栈出块、分量内去重、根与孤立点处理。 |
| 割点与块 | luogu P3225: [HNOI2012] 矿场搭建 | 统计块中的割点,判断哪些部分必须设置出口;注意多组数据、有效顶点编号与方案数。 |
| 圆方树进阶 | luogu P4630: [APIO2018] 铁人两项 | 点双分解后进行圆方树上的计数;需要继续学习树形计数,不能直接套用本篇输出模板。 |
12 相关题解
暂无相关题解