P2860 [USACO06JAN]Redundant Paths G 边双联通分量

//题意：给出一个连通图，询问至少加多少条边可以使得整个图成为一个双联通图
//思路：首先图中的双联通分量内部已经满足条件了，所以就是要将每一个双联通分量之间连起来，也就是消除割边
//      可以想到，我们将所有的双联通分量缩成一个点，那么剩下的边都是割边，也就是一棵树
//      接下来的思路看博客中的网址，大概意思就是只要保证叶子节点两两相连就可以保证整棵树变为双联通图
//      
//
#include<bits/stdc++.h>
using namespace std;
const int N = 5010;
vector<pair<int, int>> mp[N];
int n, m;
int dfn[N], low[N], idx, bel[N], stk[N], top;
int num;
bool vis[N];
vector<int> cc[N];
void dfs(int u, int id) {
    dfn[u] = low[u] = ++idx;
    stk[++top] = u;
    vis[u] = 1;
    for (auto y : mp[u]) {
        int a = y.first, b = y.second;
        if (vis[a]) {
            if (dfn[a] < dfn[u] && b != id) low[u] = min(low[u], dfn[a]);
            continue;
        }
        dfs(a, b);
        low[u] = min(low[u], low[a]);
    }
    if (low[u] == dfn[u]) {
        ++num;
        int x;
        while (1) {
            x = stk[top--];
            bel[x] = num;
            cc[num].push_back(x);
            if (x == u) break;
        }
    }
}
int main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int a, b; cin >> a >> b;
        mp[a].push_back({ b, i});
        mp[b].push_back({ a, i});
    }
    dfs(1, -1);//本题中已经保证了该图初始为一个联通图
    int ans = 0;
    for (int i = 1; i <= num; i++) {
        int cnt = 0;
        for (auto y : cc[i]) {
            for (auto x : mp[y]) {
                    cnt+=(bel[y]!=bel[x.first]);
            }
        }
        ans += (cnt == 1);
    }
    cout << (ans + 1) / 2;
    return 0;
}

题解 P2860 【[USACO06JAN]冗余路径Redundant Paths】 - 恨妹不成穹 的博客 - 洛谷博客 (luogu.com.cn)