双连通分量
2026-03-26
简介
边双连通分量
定义 dfn 表示 DFS 序,low 表示以当前点向下走能够到达的最小 dfn。
对应有向图强连通分量的定义,会发现没有横插边这种东西(无向图边是双向的),所以我们可以直接考虑怎么求桥。
具体的,如果一个节点 x 能到它的一个儿子节点 y,想要判断 x→y 是否是桥,只需要看 y 能否到达 x 或者 x 的祖先,即它是否在一个包含 x 的环里(lowy≤dfnx)。
如何统计所有双连通分量?显然,可以使用一个栈,每次将新节点放进栈中,如果一个点 x 的 dfnx=lowx,说明它无法走到祖先上,即它所有还在栈里的儿子和他自己是一个双连通分量(此时 x 与其祖先之间的边为一个桥)。
例题
Acwing 395. 冗余路径
容易发现,任意两点间存在两条不同边的路径等价于整个图是一个边双连通分量。
将原图进行缩点,令缩点后所有度数为一的点个数为 cnt,答案即为 ⌊2cnt+1⌋。
为什么?可以将所有度数为一的点左右两端一一连边,中间如果有单独的一个就随便连一个度数为一的点即可。
点双连通分量
和边双连通分量一样,一个点 x 和他的一个儿子 y,怎么判断 x 是割点呢?只需要看从 y 能不能走到 x 及其祖先上,如果 x 不是根节点,那么 x 就是一个割点;否则至少需要有两个子树满足 lowy≥x,这时候 x 即为割点(可以想想一条链)。
求完割点,怎么求点双连通分量呢?求连通分量都可以用栈来处理,我们只需要考虑什么时候出栈就可以了,显然,当 dfnx≤lowy 时出栈(这个时候 y 走不到 x 及其祖先,说明 x 为割点,也就是这一段双连通分量的顶端)。
怎么进行缩点?首先一个割点有可能属于好几个双连通分量,所以我们需要进行一些更为特殊的处理。
具体的,将每个割点单独建成一个新的点,然后让所有的双连通分量向它所包含的割点连边(注意!!!最多会有 2n 个点)。
例题
Acwing 1183. 电力
读完题目,容易发现其实答案只与割点和连通块个数有关。
具体的,如果原本有 cnt 个连通块,删除当前割点后这个连通块会裂成 s 个,答案即为 max{cnt+s−1}。
Acwing 396. 矿场搭建
概括一下题意:给定一张无向图(可能不连通),求最少设置几个出口以及其方案数,使得删掉任意一个点后,剩余的点都能够到达出口。
然后,我们对于一个连通块进行讨论:
- 无割点,显然只需要放两个出口(出口也有可能塌),方案数为 (2cnt)。
- 有割点,需要进行缩点,然后看每个连通分量的度数。如果度数为 1,也就是说这个连通分量里面必须有一个出口 cnt−1(刨去割点),方案数为;度数如果大于 1,也就是无论怎样都能走到别的出口,即不需要放出口。
