题面
题目描述
为了从 个草场中的一个走到另一个,贝茜和她的同伴们有时不得不路过一些她们讨厌的可怕的树。
奶牛们已经厌倦了被迫走某一条路,所以她们想建一些新路,使每一对草场之间都会至少有两条相互分离的路径,这样她们就有多一些选择。
每对草场之间已经有至少一条路径。
给出所有 条双向路的描述,每条路连接了两个不同的草场,请计算最少的新建道路的数量,路径由若干道路首尾相连而成。
两条路径相互分离,是指两条路径没有一条重合的道路。但是,两条分离的路径上可以有一些相同的草场。
对于同一对草场之间,可能已经有两条不同的道路,你也可以在它们之间再建一条道路,作为另一条不同的道路。
输入格式
第 行,两个用空格分隔的整数 和 。
接下来 行,每行输入两个整数,表示两个草场,它们之间有一条道路。
输出格式
一行一个整数,表示最少的需要新建的道路数。
输入输出样例
样例输入 #1
7 7
1 2
2 3
3 4
2 5
4 5
5 6
5 7
样例输出 #1
2
数据范围与约定
对于 的数据,,。
思路
由题:
两条路径相互分离,是指两条路径没有一条重合的道路。
可知:
对于图中的任意两点 之间的所有路径上,不能够存在一条边满足如果不经过它,就不能从点 到达点 。
换言之,就是不能存在一条边使得删去它后整个图变得不连通。那么题目的要求就可以转化为:给定一个连通无向图,求出加边的最小数量使得整个图变为一个双连通分量。
先求出图中所有的双连通分量并缩点,缩点之后图就变成了一棵树的形状,那么只需要对这棵树加边,使其构成双连通分量即可。
对于树上的每一个叶子节点,如果将其与它父亲节点的连边删去,那么这个节点就会被孤立,无法构成双连通分量。所以将其与其他节点再连一条边即可避免发生这种情况,一个比较显然的结论就是将这条边连向另一个叶子节点是最优的。那么对于有偶数个叶子节点的树,需要连 个点,对于有奇数个叶子节点的树,需要连 个点。整理得 。
代码
#include <iostream>
#include <cstring>
#include <stack>
using std::cin;
using std::cout;
const char endl = '\n';
const int N = 5005,
M = 10005 << 1;
int f, r, ans;
int idx, head[N], edge[N], next[N]; // 链式前向星
int cnt, dfn[N], low[N]; // Tarjan 辅助数组
int dcc_cnt, siz[N], id[N], in[N]; // 双连通分量
bool bridge[N]; // 桥边
std::stack<int> st;
void add(int u, int v) {
next[idx] = head[u];
edge[idx] = v;
head[u] = idx++;
}
// Tarjan 求双连通分量
void tarjan(int u, int in_edge) {
dfn[u] = low[u] = ++cnt;
st.push(u);
for (int i = head[u]; ~i; i = next[i]) {
int v = edge[i];
if (!dfn[v]) {
tarjan(v, i);
low[u] = std::min(low[u], low[v]);
if (dfn[u] < low[v]) {
bridge[i] = bridge[i ^ 1] = true;
}
} else if (i != (in_edge ^ 1)) {
low[u] = std::min(low[u], dfn[v]);
}
}
if (dfn[u] == low[u]) {
dcc_cnt++;
int v;
do {
v = st.top();
st.pop();
id[v] = dcc_cnt;
siz[dcc_cnt]++;
} while (v != u);
}
}
int main() {
std::ios::sync_with_stdio(false);
cin.tie(nullptr);
memset(head, 0xff, sizeof(head));
cin >> f >> r;
for (int i = 1, u, v; i <= r; i++) {
cin >> u >> v;
add(u, v);
add(v, u);
}
tarjan(1, -1);
for (int i = 0; i < idx; i++) {
if (bridge[i]) {
in[id[edge[i]]]++;
}
}
for (int i = 1; i <= dcc_cnt; i++) {
if (in[i] == 1) ans++;
}
cout << (ans + 1) / 2 << endl;
return 0;
}