题目链接:https://www.luogu.com.cn/problem/P2860
题目大意:
给定一个无向连通图,求至少加几条边,能使其变成一个边双连通图。
解题思路:
边双连通分量缩点后计算度数为 \(1\) 的节点个数,假设有 \(cnt\) 个,则答案为 \((cnt+1)/2\)。
示例程序:
#include <bits/stdc++.h>
using namespace std;
const int maxn = 5050, maxm = 20020;
struct Edge {
int u, v, nxt;
} edge[maxm];
int n, m, head[maxn], ecnt;
void init() {
memset(head, -1, sizeof(int)*(n+1));
ecnt = 0;
}
void addedge(int u, int v) {
edge[ecnt] = {u, v, head[u]}; head[u] = ecnt++;
edge[ecnt] = {v, u, head[v]}; head[v] = ecnt++;
}
int dfn[maxn], low[maxn], id[maxn], ts, dcc;
bool vis[maxm];
stack<int> stk;
void tarjan(int u) {
dfn[u] = low[u] = ++ts;
stk.push(u);
for (int i = head[u]; i != -1; i = edge[i].nxt) {
if (vis[i]) continue;
vis[i] = vis[i^1] = true;
int v = edge[i].v;
if (!dfn[v])
tarjan(v), low[u] = min(low[u], low[v]);
else
low[u] = min(low[u], dfn[v]);
}
if (dfn[u] == low[u]) {
dcc++;
int v;
do {
v = stk.top();
stk.pop();
id[v] = dcc;
} while (u != v);
}
}
int d[maxn];
int main() {
scanf("%d%d", &n, &m);
init();
for (int i = 0; i < m; i++) {
int u, v;
scanf("%d%d", &u, &v);
addedge(u, v);
}
tarjan(1);
for (int i = 0; i < 2*m; i += 2) {
int u = edge[i].u, v = edge[i].v;
if (id[u] != id[v])
d[id[u]]++, d[id[v]]++;
}
int cnt = 0;
for (int i = 1; i <= dcc; i++) if (d[i] == 1) cnt++;
printf("%d\n", (cnt + 1) / 2);
return 0;
}