双连通分量的一些例子

[[ slider_text ]]

[[ item.c ]]

双连通分量的一些例子

发布时间 2024-05-03 作者：秋千月 来源：代码源，OI-WIKI，算法小站

双连通分量 圆方树

点双和边双的一些例子
## Redundant Paths(USACO 2006)
**问题描述**
**[Redundant Paths](https://ac.nowcoder.com/acm/problem/51307)**
给定一个$$(n, m)$$的无向连通图，问最多加多少条边能形成一个边双连通图？
### 算法分析
>  原来不是边双，说明了什么？边双缩点之后，形成了一棵树

可以发现，原来不是边双，缩点之后应该是一种**树形结构**，如下图所示
![](/media/content_img/usaco-01.png)
对于树形结构，在$$(A, B)$$间添加一条边，可以发现$$A \to B$$路径上的树边，都被$$(A, B)$$所覆盖
树边被添加的边$$(A, B)$$覆盖，原来的那些边也就不是割边了

> 问题转化成，给你一棵树，选任意两个点$$(A, B)$$，构成一条路径，然后我们去覆盖这样的路径
> 最少多少次能 cover 所有的路径？

这个问题可能比较难想，回顾一下点双，注意到点双中，割点它一定在点双中不用管了
要想使得整个图是一个点双，那么要考虑非割点，点双中的非割点一定是叶子结点
类似的，边双中的叶子结点有没有同样的性质呢？

**我们是不是要把尽可能多的叶子结点都囊括进来？**
对原图进行边双缩图之后，**叶子结点一定不在任何一个边双中**，重点考虑叶子结点

>  要 cover 所有叶子，假设有$$k$$个叶子结点，那么答案至少应该是$$\displaystyle\lceil \frac{k}{2} \rceil$$次
>  至少要这么多次才能覆盖所有的叶子（因为一条路径只能覆盖两个叶子）
>  问题是，是不是$$\displaystyle\lceil \frac{k}{2} \rceil$$这么多次就够了呢？

实际上就够了，实际上如果我们考虑完全二叉树的情况，假设叶子结点均匀分布在第$$i$$层
那么非叶子结点有$$2^0 + 2^1 + \cdots + 2^{i-1} = 2^i - 1 \leqslant 2^i$$
也就是说，假设叶子结点有$$m$$个（$$m$$为偶数），那么非叶子结点的上界为$$O(m)$$
注意到，这些非叶子结点**并非每一个都需要被选，被覆盖**，只需要选出**能作为 LCA 的点**，将其覆盖
这样就可以覆盖所有子树了
$$O(m)$$个点中，实际上，能够作为 **LCA** 的点，有$$O(\lceil m/2 \rceil)$$个
所以$$\lceil m/2 \rceil$$次的叶子覆盖，就一定能覆盖所有子树

> 那么怎么构造方案？

![](/media/content_img/usaco-02.png)
假设叶子结点的个数为$$m$$
对叶子按照 **dfs 序**排序，对于编号为$$i$$的叶子，$$(i, m/2)$$连边，这样一定可以覆盖子树
证明见上图

### 算法实现
对原图进行边双缩图，缩图之后得到的树，答案是$$\lceil C/2 \rceil$$，其中$$C$$是叶子个数
判断叶子很简单
```bash
for 每一个连通分量 dcc(i):
		如果连通块 i 只有一个割边的话，这个块就是缩点之后的叶子
```
核心代码如下
```bash
int idx = 0;
stack<int> stk;
int cnt = 0;
function<void(int, int)> dfs = [&](int u, int id) -> void {
	dfn[u] = low[u] = ++idx;
	stk.push(u);

for (auto [v, id2] : G[u]) {
		if (!dfn[v]) {
			dfs(v, id2);
			low[u] = min(low[u], low[v]);
		}
		else if (id != id2) low[u] = min(low[u], dfn[v]);
	}
	
	if (low[u] == dfn[u]) {
		if (id != 0) bridge.push_back(id), isbridge[id] = 1;
		++cnt;
		while (true) {
			auto v = stk.top();
			stk.pop();
			edcc[cnt].push_back(v), bel[v] = cnt;
			if (v == u) break;
		}
	}
};
dfs(1, 0);
// 统计叶子
int nleaf = 0;
for (int i = 1; i <= cnt; i++) {
	int cnte = 0;
	for (auto u : edcc[i]) for (auto [v, id] : G[u]) {
		cnte += (bel[u] != bel[v]);
	}
	nleaf += (cnte == 1);
}
```

## BLO(POI 2008)
**问题描述**
**[BLO(POI 2008)](https://www.luogu.com.cn/problem/P3469)**
给定一个$$(n,m)$$的无向图，对每个点，输出删点之后，有多少点对不互相连通？注意$$(u, v)$$不相连通的话
$$(u, v), (v, u)$$算`2`次

### 算法分析
根据题目就能猜到，和点双有关
>  考虑删点的过程，会发生什么？
![](/media/content_img/blo-01.png)

> 简单情况，如果删的点不是割点？

不是割点，不影响剩下的点的连通性，剩下的$$(n-1)$$个点依然连通，只有被删去的那一个点断开了
答案是$$2\cdot (n-1) = 2n - 2$$

> 如果删了割点是什么情况呢？

可以考虑[APIO 2018 铁人两项](https://www.ringalgo.com/article/20/)的分析
![](/media/content_img/blo-02.png)

## 矿场搭建(HNOI2012)
**问题描述**
**[矿场搭建HNOI2012](https://ac.nowcoder.com/acm/problem/20099)**
给定一个无向图$$(n, m)$$，要求给一些点设置救援点，使得删除任意一个点，每个连通块**至少有一个救援出口**
问，至少需要设置几个救援出口？不同最少救援出口的设置方案总数？

### 算法分析

>  考虑简单情况，整个图都是点双？

此时要放置`2`个安全出口，这样保证了一个安全出口炸了，但整个图还是连通的（因为点双要炸`2`个点才不连通）
如果只放一个的话，这个点炸了就没有出口了，这两个安全出口**任意**放置都可以
答案是$$\displaystyle \binom{n}{2}$$，放$$2$$个安全出口

>  对于一般图，缩点成 Block-Tree

![](/media/content_img/HNOI2012-01.png)

这种情况，我们需要处理**缩点后，相当于叶子结点的连通块**，每一个这样的连通块，都应该放置$$1$$个出口
当然，这样的连通块可以在叶子结点处任意放置

* 检查每一个方点，`for 方点 x 的所有邻居 u`，如果`u`是割点，`cutnum += 1`
  对于`cutnum = 1`的方点，我们应该放置一个安全出口，`ans += 1`
  
* 另外，对于这样的方点，可以在$$deg - 1$$个叶子结点处任意放出口，`way *= (deg - 1)`

上一篇：无向图的割点，割边，双连通分量下一篇：树形动态规划（树形背包）

看完文章有啥想法