|
|
## [$AcWing$ $395$. 冗余路径](https://www.acwing.com/problem/content/description/397/)
|
|
|
|
|
|
### 一、题目描述
|
|
|
为了从 $F$ 个草场中的一个走到另一个，奶牛们有时不得不路过一些她们讨厌的可怕的树。
|
|
|
|
|
|
奶牛们已经厌倦了被迫走某一条路，所以她们想建一些新路，使每一对草场之间都会 **至少有两条相互分离的路径** ，这样她们就有多一些选择。
|
|
|
|
|
|
**每对草场之间已经有至少一条路径**。
|
|
|
|
|
|
给出所有 $R$ 条 **双向路** 的描述，每条路连接了两个不同的草场，请计算 **最少** 的新建道路的数量，路径由若干道路首尾相连而成。
|
|
|
|
|
|
**两条路径相互分离，是指两条路径没有一条重合的道路。**
|
|
|
|
|
|
**但是，两条分离的路径上可以有一些相同的草场。**
|
|
|
|
|
|
对于同一对草场之间，可能已经有两条不同的道路，你也可以在它们之间再建一条道路，作为另一条不同的道路。
|
|
|
|
|
|
**输入格式**
|
|
|
第 $1$ 行输入 $F$ 和 $R$。
|
|
|
|
|
|
接下来 $R$ 行，每行输入两个整数，表示两个草场，它们之间有一条道路。
|
|
|
|
|
|
**输出格式**
|
|
|
输出一个整数，表示 **最少** 的 **需要新建的道路数**。
|
|
|
|
|
|
**数据范围**
|
|
|
$1≤F≤5000,F−1≤R≤10000$
|
|
|
|
|
|
**输入样例**：
|
|
|
```cpp {.line-numbers}
|
|
|
7 7
|
|
|
1 2
|
|
|
2 3
|
|
|
3 4
|
|
|
2 5
|
|
|
4 5
|
|
|
5 6
|
|
|
5 7
|
|
|
```
|
|
|
|
|
|
**输出样例**：
|
|
|
```cpp {.line-numbers}
|
|
|
2
|
|
|
```
|
|
|
|
|
|
### 二、前导知识
|
|
|
|
|
|
**[无向图的双连通分量](https://www.cnblogs.com/littlehb/p/16091406.html)**
|
|
|
|
|
|
### 三、题目解析
|
|
|
|
|
|
从题目描述中的 **每一对草场之间都会至少有两条相互分离的路径** 和 **两条路径相互分离，是指两条路径没有一条重合的道路**，可以知道这其实就是 **边双连通图** 的定义。
|
|
|
|
|
|
在同一个边双连通分量中，任意两点都有至少两条独立路径可达，所以同一个边双连通分量里的所有点可以看做同一个点，于是可以把一个边双连通分量进行 **缩点**。把所有的边双连通分量都进行缩点后，那么 **就会形成一棵树**。树中的节点就是边双连通分量缩完之后的点，而树中的边其实就是 **割边**。
|
|
|
|
|
|
题目是说要新建一些道路，使得它成为边双连通图。那么转化为：在树中至少添加多少条边能使图变为边双连通图
|
|
|
|
|
|
这里有一个 **定理**：统计出树中度为$1$的结点的个数，即叶结点的个数，记为 $leaf$ ，则要使树中任意两个节点之间都有两条独立的路径，则需要添加的边数为$\large ⌊\frac {leaf+1}{2}⌋$
|
|
|
|
|
|
可以用下面的栗子来解释一下：
|
|
|
|
|
|
- **当叶子节点的个数$leaf$为偶数时**：
|
|
|
|
|
|
|
|
|
|
|
|
- **当叶子节点的个数$leaf$为奇数时**：
|
|
|
|
|
|
|
|
|
|
|
|
综上，结合$\dfrac {leaf}{2}$ 和$\dfrac {leaf+1}{2}$ 答案就是$\dfrac {leaf+1}{2}$ 向下取整
|
|
|
|
|
|
|
|
|
#### 算法设计
|
|
|
|
|
|
- ① 先把原图建立出来
|
|
|
- ② $tarjan$求割边，同时求出边连通分量，缩点
|
|
|
- ③ 遍历每一条边，找到割边，设这条割边的两个端点为$x , y$，节点$x$所在的边连通分量为$a=id[x]$，节点$y$所在的边连通分量为$b=id[y]$，分别统计$a,b$的度
|
|
|
- ④ 遍历这$e\_dcc$个边连通分量，其实也就是缩完之后的$e\_dcc$个点，统计入度为$1$的顶点个数，最终答案就是$\dfrac {leaf+1}{2}$ 向下取整
|
|
|
|
|
|
|
|
|
### $Code$
|
|
|
```cpp {.line-numbers}
|
|
|
#include <bits/stdc++.h>
|
|
|
using namespace std;
|
|
|
|
|
|
const int N = 5010, M = 20010;
|
|
|
|
|
|
int n, m;
|
|
|
int d[N]; // 边双连通分量块的度
|
|
|
|
|
|
// 链式前向星
|
|
|
int e[M], h[N], idx, w[M], ne[M];
|
|
|
void add(int a, int b, int c = 0) {
|
|
|
e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
|
|
|
}
|
|
|
|
|
|
// 边双连通分量
|
|
|
int dfn[N], low[N], ts, stk[N], top, root;
|
|
|
vector<int> bcc[N]; // 边双中有哪些原始点,集合-> 点
|
|
|
int id[N], bcnt; // 原始点x属于哪个边双连通分量，bcnt指边双连通分量个数,点->集合
|
|
|
int is_bridge[M]; // 哪些边是割边
|
|
|
|
|
|
void tarjan(int u, int fa) {
|
|
|
dfn[u] = low[u] = ++ts;
|
|
|
stk[++top] = u;
|
|
|
for (int i = h[u]; ~i; i = ne[i]) {
|
|
|
int v = e[i];
|
|
|
if (!dfn[v]) {
|
|
|
tarjan(v, i);
|
|
|
low[u] = min(low[u], low[v]);
|
|
|
if (dfn[u] < low[v]) is_bridge[i] = is_bridge[i ^ 1] = 1; // 记录割边
|
|
|
} else if (i != (fa ^ 1))
|
|
|
low[u] = min(low[u], dfn[v]);
|
|
|
}
|
|
|
|
|
|
if (dfn[u] == low[u]) {
|
|
|
++bcnt; // 边双号
|
|
|
int x;
|
|
|
do {
|
|
|
x = stk[top--];
|
|
|
id[x] = bcnt; // 记录点与边双关系
|
|
|
bcc[bcnt].push_back(x); // 记录边双中有哪些点
|
|
|
} while (x != u);
|
|
|
}
|
|
|
}
|
|
|
|
|
|
int main() {
|
|
|
memset(h, -1, sizeof h);
|
|
|
scanf("%d %d", &n, &m);
|
|
|
while (m--) {
|
|
|
int a, b;
|
|
|
scanf("%d %d", &a, &b);
|
|
|
if (a != b) add(a, b), add(b, a);
|
|
|
}
|
|
|
// Tarjan算法缩点，生成边双连通分量, 缩点后，新图中的边将只是割边。
|
|
|
// 注意：这里并没有真的创建新图，而是心中有图而手中无图。
|
|
|
// 获取边双连通分量的过程中，记录了哪些边是割边，下面将利用割边解决问题
|
|
|
for (root = 1; root <= n; root++)
|
|
|
if (!dfn[root]) tarjan(root, -1);
|
|
|
|
|
|
// 下面统计新图中每个点的度,这是一个经典用法，需要理解和记忆
|
|
|
// 计算新图中度为1的点(边双连通分量)的个数，也就是叶子节点的个数
|
|
|
for (int u = 1; u <= n; u++) // ①枚举每个原始点
|
|
|
for (int i = h[u]; ~i; i = ne[i]) { // ②枚举此点的每条出边
|
|
|
// (1) 由于每个节点都可以从1~n枚举到，所以u->v,v->u也都可以被枚举到
|
|
|
// (2) 由于割边是成对出现，而成对的割边都可以通过出边的方式被枚举到，也就是成对的割边
|
|
|
// 为两个节点都提供了一个度，这个度可以理解为在无向图中某个点的连接边数，
|
|
|
// 这个边数可不是a->b,b->a这样的形式，只是a-b
|
|
|
int v = e[i];
|
|
|
// 如果某条边是割边，说明它在新图中是存在的边
|
|
|
if (is_bridge[i]) d[id[v]]++; // 如果此边是割边,则新点的度++
|
|
|
}
|
|
|
|
|
|
// 度为1的是叶子
|
|
|
int cnt = 0;
|
|
|
for (int i = 1; i <= bcnt; i++) // 注意：模板中的bcnt是从1开始的
|
|
|
if (d[i] == 1) cnt++; // 多少个度为1的节点(边双连通分量)
|
|
|
|
|
|
// 贪心,叶子结点的除以2上取整即是答案
|
|
|
printf("%d\n", (cnt + 1) / 2);
|
|
|
return 0;
|
|
|
}
|
|
|
``` |
