题意：有F个牧场，1<=F<=5000，现在一个牧群经常需要从一个牧场迁移到另一个牧场。奶牛们已经厌烦老是走同一条路，所以有必要再新修几条路，这样它们从一个牧场迁移到另一个牧场时总是可以选择至少两条独立的路。现在F个牧场的任何两个牧场之间已经至少有一条路了，奶牛们需要至少有两条。 给定现有的R条直接连接两个牧场的路，F-1<=R<=10000，计算至少需要新修多少条直接连接两个牧场的路，使得任何两个牧场之间至少有两条独立的路。两条独立的路是指没有公共边的路，但可以经过同一个中间顶点
思路：求出所有的桥，然后根据桥建图，这个图是一棵树，让这个树加边变成双连通图，加最少的边是多少，可以求出度为1的点，就是叶节点的个数，记为leaf。则至少在树上添加(leaf+1)/2条边，就能使树达到边二连通，所以至少添加的边数就是(leaf+1)/2。
#include<iostream> #include<algorithm> #include<stack> #include<cstring> #define ll long long using namespace std; const int N = 1e5 + 10; int n, m, t, h[N], cnt, ans; int inde, dfn[N], low[N], scc[N], ins[N], sum, du[N]; stack<int> s; struct node { int v, net; } no[N]; void add(int u, int v) { no[cnt].v = v; no[cnt].net = h[u]; h[u] = cnt++; } void init() { sum = cnt = inde = 0; memset(dfn, 0, sizeof dfn); memset(h, -1, sizeof h); memset(ins, 0, sizeof ins); } void tarjan(int u, int edge) { dfn[u] = low[u] = ++inde; ins[u] = 1; s.push(u); int f = 0; for(int i = h[u]; ~i; i = no[i].net) { int v = no[i].v; if(v == edge && !f) { f = 1; continue; } if(!dfn[v]) { tarjan(v, u); low[u] = min(low[v], low[u]); } else if(ins[v]) low[u] = min(low[u], dfn[v]); } if(low[u] == dfn[u]) { sum++; while(s.top() != u) { int v = s.top(); scc[v] = sum, ins[v] = 0; s.pop(); } s.pop(); ins[u] = 0, scc[u] = sum; } } int main() { init(); cin >> n >> m; for(int x, y, i = 0; i < m; i++) { cin >> x >> y; add(x, y); add(y, x); } for(int i = 1; i <= n; i++) if(!dfn[i]) tarjan(i, -1); for(int u = 1; u <= n; u++) for(int i = h[u]; ~i; i = no[i].net) if(scc[no[i].v] != scc[u]) du[scc[u]]++; for(int i = 1; i <= n; i++) if(du[i] == 1) ans++; cout << (ans + 1) / 2;; return 0; }
