边的双连通分量
作者:
艾特玖
,
2021-08-12 19:04:41
,
所有人可见
,
阅读 271
无向图
双连通分量
1 边的双连通分量 e-dcc 极大的不包含桥的连通块
2 点的双连通分量 v-dcc 极大的不包含割点的连通块
删除后不连通 的 两个定义
桥
o-o 桥o-o
| | ↓ | |
o-o - o-o
1 如何找桥? x
/
y
x和y之间是桥 <=> dfn[x] < low[y] y无论如何往上走不到x
+y能到的最高的点low[y] = dfn[y]
2 如何找所有边的双连通分量?
2.1 将所有桥删掉
2.2 stack
dfn[x] == low[x]
<=> x无论如何走不到x的上面
<=> 从x开始的子树可以用一个栈存
每个割点至少属于两个连通分量
树里的每条边都是桥
o
/ \
o o
/\ /\
o o o o
1 边双连通分量
tarjan回顾
dfn[x] dfs序时间戳
low[x] x能达到的时间戳最小的点
无向图不存在横插边
o
/ \
o o
/ / \
y ← x o
→
x能往左的话 由于无向边 所以y也能往右,
那么在之前dfs的时候就把x先于x的父节点加进来了
*/