洛谷 P2860 Redundant Paths G

洛谷 P2860 Redundant Paths G

题意

给定一张图，求最少添加几条边使得原图变为边双连通图。

思路

先将原图进行边双连通分量缩点，因为已经边双连通的子图我们不用考虑。

缩点后会得到一棵树，每一条边都是桥。假定有 \(k\) 个叶子节点。

我们可以把叶子节点两个两个配对连边形成环，这样可以把树变成边双连通。

答案为 \(\lceil \frac{k}{2}\rceil\)。因为 \(k\) 为奇数时，单独留下的那个点也要连边。

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 5005, M = 100005;
int tot = 1, ver[M << 1], nxt[M << 1], head[N];
int n, m, low[N], dfn[N], cnt, ec, ecc[N], in[N], c;
bool b[M << 1], vis[N];
void add(int x, int y) {
	ver[++ tot] = y;
	nxt[tot] = head[x];
	head[x] = tot;
}
void tarjan(int x, int fa) {
	low[x] = dfn[x] = ++ cnt;
	for (int i = head[x], y; i; i = nxt[i]) {
		y = ver[i];
		if (!dfn[y]) {
			tarjan(y, x);
			if (low[y] > dfn[x]) b[i] = b[i ^ 1] = 1;
			low[x] = min(low[x], low[y]);
		} else if (y != fa)
			low[x] = min(low[x], dfn[y]);
	}
}
void dfs(int x) {
	ecc[x] = ec;
	for (int i = head[x], y; i; i = nxt[i]) {
		if (b[i]) continue;
		if (vis[y = ver[i]]) continue;
		vis[y] = 1;
		dfs(y);
	}
}
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1, u, v; i <= m; i ++) {
		scanf("%d%d", &u, &v);
		add(u, v), add(v, u);
	}
	tarjan(1, 0);
	for (int i = 1; i <= n; i ++) if (!vis[i]) {
		ec ++; dfs(i);
	}
	for (int i = 1; i <= n; i ++) 
		for (int j = head[i], y; j; j = nxt[j]) {
			if (ecc[i] == ecc[y = ver[j]]) continue;
			in[ecc[y]] ++;
		}
	for (int i = 1; i <= ec; i ++) c += (in[i] == 1);
	printf("%d\n", (c >> 1) + (c & 1));
	return 0;
}