题目描述
为了从 F 个草场中的一个走到另一个,奶牛们有时不得不路过一些她们讨厌的可怕的树。
奶牛们已经厌倦了被迫走某一条路,所以她们想建一些新路,使每一对草场之间都会至少有两条相互分离的路径,这样她们就有多一些选择。
每对草场之间已经有至少一条路径。
给出所有 R 条双向路的描述,每条路连接了两个不同的草场,请计算最少的新建道路的数量,路径由若干道路首尾相连而成。
两条路径相互分离,是指两条路径没有一条重合的道路。
但是,两条分离的路径上可以有一些相同的草场。
对于同一对草场之间,可能已经有两条不同的道路,你也可以在它们之间再建一条道路,作为另一条不同的道路。
输入格式
第 1 行输入 F 和 R。
接下来 R 行,每行输入两个整数,表示两个草场,它们之间有一条道路。
输出格式
输出一个整数,表示最少的需要新建的道路数。
数据范围
1≤F≤5000,
F−1≤R≤10000
样例
7 7
1 2
2 3
3 4
2 5
4 5
5 6
5 7
2
算法1
(tarjan缩点) $O(n + m)$
本题目的目标是:将一个连通图,至少增加多少条边,使得任意两点之间能够通过两条互不相交的路径到达(两条路径中没有一条边是重合的)
结论:任意两点之间能够通过两条互不相交的路径到达 <-> 边双连通分量
证明要从充分性和必要性去论证
充分性:(反证法)如果说任意两点之间能够通过两条互不相交的路径到达,不是边双连通分量,那么两个连通分量之间存在桥,从两个连通分量中各任选一点,它们一定会经过桥连通,因此必然是会走同一条边(桥)矛盾
必要性:边双连通分量是否一定满足任意两点之间能够通过两条互不相交的路径到达
边双连通分量不含有桥,那么任意相邻两点之间必然至少存在两条道路,因此任意两点之间必然存在两条互不相交的路径
将一个无向连通图缩点后,必然是一棵树(不存在环)既然是一棵树,因为叶子节点的度数为1,那么从根节点走到叶子节点的路径必然是会有重复边的。同时任意连接两点,就一定会形成一个环,那么我们如果将两两叶子节点连接起来,整个树就会变成一个闭环图。答案就是 (cnt + 1) / 2,(cnt是叶子节点数量)但是有一个细节:就是假设根节点root下面有很多子树,子树内部的叶子节点不能相连,因为相连了之后将根节点和子树的边删除后,图变得不连通了,这是一个桥,所以增加这条边一定比删除它更优
时间复杂度
参考文献
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 5010,M = 20010;
int n,m;
int h[N],e[M],ne[M],idx;
int dfn[N],low[N],timestamp;
int stk[N],top;
bool is_bridge[M]; // 判断是否是桥
int id[N],dcc_cnt;
int d[N]; // 统计一下每个连通分量的度数
void add(int a,int b){
e[idx] = b,ne[idx] = h[a],h[a] = idx ++;
}
// from记录每个点u是从哪条边过来的
void tarjan(int u,int from){
dfn[u] = low[u] = ++ timestamp;
stk[ ++ top ] = u;
for(int i = h[u];~i;i = ne[i]){
int j = e[i];
if(!dfn[j]){
tarjan(j,i);
low[u] = min(low[u],low[j]);
if(dfn[u] < low[j]) is_bridge[i] = is_bridge[i ^ 1] = true; // 每条边都是存两次,因此所有的边都是 01 12 23 一偶一奇
}else if(i != (from ^ 1)) low[u] = min(low[u],dfn[j]); // i 不是反向边
}
if(dfn[u] == low[u]){
dcc_cnt ++;
int y;
do{
y = stk[ top -- ];
id[y] = dcc_cnt;
}while(y != u);
}
}
int main()
{
cin >> n >> m;
memset(h, -1, sizeof h);
while(m -- ){
int a,b;
cin >> a >> b;
add(a,b),add(b,a);
}
// 将所有边双连通分量缩点,最后形成一棵树
tarjan(1,-1);
// 统计每个双连通分量的度数
for(int i = 0;i<idx;i++){
if(is_bridge[i])
d[id[e[i]]] ++;
}
// 统计有多少个叶子结点
int cnt = 0;
for(int i = 1;i <= dcc_cnt;i++)
if(d[i] == 1)
cnt ++;
printf("%d\n",(cnt + 1) / 2);
return 0;
}