洛谷P2860 [USACO06JAN] Redundant Paths G 题解 边双连通分量

题目链接：https://www.luogu.com.cn/problem/P2860

解题思路：

双连通分量缩点，设缩点后有 \(cnt\) 个度数为 \(1\) 的点。

则答案为 \(\lceil \frac{cnt}{2} \rceil\)（即 (cnt + 1) / 2）。

示例程序：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e4 + 5, maxm = 1e5 + 5;struct Edge {int v, id;
};
vector<Edge> g[maxn];
int n, m, dfn[maxn], low[maxn], ts, dcc, bl[maxn], d[maxn], cnt;
stack<int> stk;void tarjan(int u, int eid) {dfn[u] = low[u] = ++ts;stk.push(u);for (auto &[v, id] : g[u]) {if (id == eid) continue;if (!dfn[v]) tarjan(v, id);low[u] = min(low[u], low[v]);}if (low[u] == dfn[u]) {dcc++;int v;do {v = stk.top();stk.pop();bl[v] = dcc;} while (u != v);}
}int main() {scanf("%d%d", &n, &m);for (int i = 1, u, v; i <= m; i++) {scanf("%d%d", &u, &v);g[u].push_back({v, i});g[v].push_back({u, i});}for (int i = 1; i <= n; i++)if (!dfn[i])tarjan(i, -1);for (int u = 1; u <= n; u++)for (auto &[v, id] : g[u])if (bl[u] < bl[v]) // 避免 (u,v) 和 (v,u) 重复算d[ bl[u] ]++, d[ bl[v] ]++;for (int i = 1; i <= dcc; i++)if (d[i] == 1)cnt++;printf("%d\n", (cnt + 1) / 2);return 0;
}