为了从 $F$ 个草场中的一个走到另一个，贝茜和她的同伴们不得不路过一些她们讨厌的可怕的树。奶牛们已经厌倦了被迫走某一条路，所以她们想建一些新路，使每一对草场之间都会至少有两条相互分离的路径，这样她们就有多一些选择。
每对草场之间已经有至少一条路径，给出所有 $R$ 条双向路的描述，每条路连接了两个不同的草场，请计算最少的新建道路的数量。
路径由若干道路首尾相连而成，两条路径相互分离，是指两条路径没有一条重合的道路，但是两条分离的路径上可以有一些相同的草场。
对于同一对草场之间，可能已经有两条不同的道路，你也可以在它们之间再建一条道路，作为另一条不同的道路。
链接
题解
在一个边双连通图里的点之间的连边是不会减少桥的数目的。缩点后得到的图必然是一棵树，在这棵树中，如果每两个叶子节点连上一条边，就可以用最少的边使树达到边双连通。
具体步骤：
-
先用 Tarjan 求边双连通分量，并缩点；
-
计算缩点后每个点边的数目，如果为 1，则是叶子节点；
-
统计叶子节点数目，$ m{ans}=(leaf+1) div 2$。
因为是双向建边，故需要一个 $mathrm{vis}$ 值记录方向边是否被访问。
代码
vis[i] 记录序号为 $i$ 的边是否被访问过。
i & 1 ? (i + 1) : (i - 1) 表示与序号为 $i$ 的边方向相反的边，由建边方式所决定。
注意：在 tarjan 函数中，vis 初始值为零，故当值为零时，表示未访问；当求叶子数目时，vis 值非零，故当值为非零时，表示未访问。
#include <cstdio>
const int vSIZE = 100005;
const int eSIZE = 400005;
int line[vSIZE];
int bcc[vSIZE], bccTot, vis[vSIZE];
int st[vSIZE], top;
int low[vSIZE], dfn[vSIZE], time;
int h[eSIZE], to[eSIZE], nxt[eSIZE], tot;
int min(int x, int y) {
return x < y ? x : y;
}
void add(int x, int y) {
to[++tot] = y;
nxt[tot] = h[x];
h[x] = tot;
}
void tarjan(int x) {
low[x] = dfn[x] = ++time;
st[++top] = x;
for (int i = h[x]; i; i = nxt[i]) {
if (!vis[i & 1 ? (i + 1) : (i - 1)]){
vis[i] = 1;
int y = to[i];
if (!dfn[y]) {
tarjan(y);
low[x] = min(low[x], low[y]);
} else {
low[x] = min(low[x], dfn[y]);
}
}
vis[i] = 1;
}
if (low[x] >= dfn[x]) {
bcc[x] = ++bccTot;
while (st[top] != x) {
bcc[st[top--]] = bccTot;
}
top--;
}
}
int main() {
int n, m, ans = 0, leaf = 0;
scanf("%d %d", &n, &m);
for (int i = 1; i <= m; i++) {
int x, y;
scanf("%d %d", &x, &y);
add(x, y);
add(y, x);
}
for (int i = 1; i <= n; i++) if(!dfn[i]) tarjan(i);
for (int i = 1; i <= n; i++) {
for (int j = h[i]; j; j = nxt[j]) {
if (vis[j & 1 ? (j + 1) : (j - 1)]){
if (bcc[i] != bcc[to[j]]) {
line[bcc[i]]++;
line[bcc[to[j]]]++;
}
}
vis[j] = 0;
}
}
for (int i = 1; i <= bccTot; i++) if (line[i] == 1) leaf++;
ans = (leaf + 1) >> 1;
printf("%d
", ans);
return 0;
}