主页
搜索
最近更新
数据统计
申请密钥
系统公告
1
/
1
请查看完所有公告
P8436 【模板】边双连通分量 题解
最后更新于 2025-07-30 23:27:32
作者
Jeremiahy
分类
题解
题解
P8436
复制 Markdown
查看原文
删除文章
更新内容
更新:2022.9.21 修正代码。 前置知识:[割边](https://www.cnblogs.com/ljy-endl/p/11595161.html) # 边双连通分量 ### 概念 若一张无向连通图不存在桥(割边),则称它为“边双连通图”。 无向图的极大边双联通子图被称为“边双联通分量”,简记为“e-DCC”。 在上面的定义中,我们称一个双连通子图 $G'=(V',E')$ “极大”(其中 $V'\subseteq V$, $E'\subseteq E$),是指不存在包含 $G'$ 的更大的子图 $G''=(V'',E'')$,满足 $V'\subseteq V''\subseteq V$, $E' \subseteq E''\subseteq E$ 并且 $G''$ 也是双连通子图。 ### 定理 一张无向图时“边双连通图”,当且仅当任意一条边都包含在至少一个简单环中。 ### 求法 只需求出无向图中所有的桥,把桥都删除后,无向图会分成若干个连通块,每一个联通块都是一个“边双连通分量”。 在具体的程序实现中,一般先用 Tarjan 算法标记出所有的桥边。然后,再对整个无向图执行一次深度优先遍历(遍历的过程中不访问桥边),划分出每个连通块。 ### 代码 ```cpp #include<bits/stdc++.h> using namespace std; const int N = 2000010, M = 6000010; int head[N], ver[M * 2], Next[M * 2]; int dfn[N], low[N], c[N];//c[x] 表示节点 x 所属的“边双连通分量”的编号。 int n, m, tot = 1, num, dcc; bool bridge[N * 2]; vector<int> ans[N * 2]; //存储各个连通块及其内部节点编号 void add(int x, int y) {//邻接表存图 ver[++tot] = y, Next[tot] = head[x], head[x] = tot; } void tarjan(int x, int in_edge) { //求割边 dfn[x] = low[x] = ++num; for (int i = head[x]; i; i = Next[i]) { int y = ver[i]; if (!dfn[y]) { tarjan(y, i); low[x] = min(low[x], low[y]); if (low[y] > dfn[x]) bridge[i] = bridge[i ^ 1] = true; } else if (i != (in_edge ^ 1)) low[x] = min(low[x], dfn[y]); } } void dfs(int x) { c[x] = dcc; if (x) //防止加入 0 ans[dcc].push_back(x); for (int i = head[x]; i; i = Next[i]) { int y = ver[i]; if (c[y] || bridge[i]) continue; dfs(y); } } int main(){ ios::sync_with_stdio(false); //关闭与 scanf 的同步来提速 cin >> n >> m; for (register int i = 1; i <= m; i++) { int x, y; cin >> x >> y; add(x, y), add(y, x); } for (register int i = 1; i <= n; i++) if (!dfn[i]) tarjan(i, 0); for (register int i = 1; i <= n; i++) if (!c[i]) { ++dcc; dfs(i); } cout << dcc << "\n"; for (register int i = 1; i <= dcc; i++) { //输出 cout << ans[i].size(); for (register int j = 0; j < ans[i].size(); j++) cout << ' ' << ans[i][j]; cout << "\n"; } return 0; } ``` ### 推荐 推荐联系配套的[点双连通分量](https://www.luogu.com.cn/problem/P8435)。 注:本文抄自 lyd 蓝书。
正在渲染内容...
点赞
32
收藏
0