題目#
為了從 F (1≤F≤5000) 個草場中的一個走到另一個，貝茜和她的同伴們有時不得不路過一些她們討厭的可怕的樹．奶牛們已經厭倦了被迫走某一條路，所以她們想建一些新路，使每一對草場之間都會至少有兩條相互分離的路徑，這樣她們就有多一些選擇．
每對草場之間已經有至少一條路徑．給出所有 R (F-1≤R≤10000) 條雙向路的描述，每條路連接了兩個不同的草場，請計算最少的新建道路的數量，路徑由若干道路首尾相連而成．兩條路徑相互分離，是指兩條路徑沒有一條重合的道路．但是，兩條分離的路徑上可以有一些相同的草場．對於同一對草場之間，可能已經有兩條不同的道路，你也可以在它們之間再建一條道路，作為另一條不同的道路．
輸入格式：
Line 1: 兩個以空格分隔的整數: F 和 R
Lines 2..R+1: 每行包含兩個以空格分隔的整數，它們是某條路徑的端點。
輸出格式：
Line 1: 一個整數，表示必須建造的新路徑數量。
輸入輸出範例
輸入範例 #1：
7 7
1 2
2 3
3 4
2 5
4 5
5 6
5 7
輸出範例 #1：
2
思路#
這是一道一本通上的模板題。求一個有橋的聯通圖通過加邊變成邊雙聯通圖，需要加的邊數，
先刪除所有的橋，剩下的是一些邊雙聯通分量。把把每個邊雙聯通分量縮成一個頂點，加回橋，最後剩下的會是一棵樹。
設這棵樹葉節點的數量為 leaf，則需要加的邊數為leaf == 1 ? 0 : (leaf + 1) / 2。這裡的除號是整除。
這是經過測試的！！
代碼#
#include <cstdio>
#include <iostream>
#include <stack>
#include <cmath>
using std::stack;
using std::min;
const int MAXN = 40000 + 5;
namespace m1 {
struct ed {
int to, nex, frm;
} e[MAXN];
int head[MAXN];
int newp = 1;
int low[MAXN], dfn[MAXN], out[MAXN];
int tim;
int dcnt;//雙聯通分量編號
int dcolor[MAXN];//雙聯通分量染色
bool bridge[MAXN];
void insert (int p1, int p2);
void tarjan (int p, int ed);
void dfs (int p);
}
int n, m;
int main (void) {
{
using namespace m1;
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; ++i) {
int x, y;
scanf("%d%d", &x, &y);
insert(x, y);
insert(y, x);
}
tarjan(1, 0);
for (int i = 1; i <= n; ++i) {
if (!dcolor[i]) {
++dcnt;
dfs(i);
}
}
for (int i = 1; i <= m; ++i) {
if (dcolor[e[i * 2].frm] != dcolor[e[i * 2].to]) {
++out[dcolor[e[i * 2].frm]];
++out[dcolor[e[i * 2].to]];
}
}
int leaf = 0;
for (int i = 1; i <= dcnt; ++i) {
if (out[i] == 1) {
++leaf;
}
}
printf("%d\n", leaf == 1 ? 0 : (leaf + 1) / 2);
}
return 0;
}
void m1::insert (int p1, int p2) {
++newp;
e[newp].frm = p1;
e[newp].to = p2;
e[newp].nex = head[p1];
head[p1] = newp;
}
void m1::tarjan (int p, int ed) {
dfn[p] = low[p] = ++tim;
for (int i = head[p]; i; i = e[i].nex) {
int y = e[i].to;
if (!dfn[y]) {
tarjan(y, i);
low[p] = min(low[p], low[y]);
if (dfn[p] < low[y]) {
bridge[i] = bridge[i ^ 1] = 1;
}
}
else if (i != (ed ^ 1)) {
low[p] = min(low[p], dfn[y]);
}
}
}
void m1::dfs (int p) {
using namespace m1;
dcolor[p] = dcnt;
for (int i = head[p]; i; i = e[i].nex) {
int y = e[i].to;
if (dcolor[y] != 0 || bridge[i] == 1) {
continue;
}
dfs(y);
}
}