传送门：Redundant Paths
题意：有n个牧场，Bessie 要从一个牧场到另一个牧场，要求至少要有2条独立的路可以走。现已有m条路，求至少要新建多少条路，使得任何两个牧场之间至少有两条独立的路。两条独立的路是指：没有公共边的路，但可以经过同一个中间顶点。
分析：在同一个边双连通分量中，任意两点都有至少两条独立路可达，因此同一个边双连通分量里的所有点可以看做同一个点。
缩点后，新图是一棵树，树的边就是原无向图的桥。
现在问题转化为：在树中至少添加多少条边能使图变为双连通图。
结论：添加边数=（树中度为1的节点数+1）/2。
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cstdlib>
#include <stack>
#include <vector>
#include <set>
#include <map>
#define LL long long
#define mod 100000000
#define inf 0x3f3f3f3f
#define eps 1e-6
#define N 10010
#define FILL(a,b) (memset(a,b,sizeof(a)))
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define PII pair<int,int>
using namespace std;
struct edge
{
int v,next;
edge(){}
edge(int v,int next):v(v),next(next){}
}e[N<<1];
int n,step,scc,top,tot;
int head[N],dfn[N],low[N],belong[N],Stack[N],du[N];
bool instack[N],vis[N<<1];
void init()
{
tot=0;top=0;scc=0;
FILL(head,-1);FILL(dfn,0);
FILL(low,0);FILL(instack,false);
FILL(du,0);FILL(vis,0);
}
void addedge(int u,int v)
{
e[tot]=edge(v,head[u]);
head[u]=tot++;
}
void tarjan(int u)
{
int v;
dfn[u]=low[u]=++step;
Stack[top++]=u;
instack[u]=true;
for(int i=head[u];~i;i=e[i].next)
{
v=e[i].v;
if(vis[i])continue;
vis[i]=vis[i^1]=1;
if(!dfn[v])
{
tarjan(v);
if(low[u]>low[v])low[u]=low[v];
}
else if(instack[v])
{
if(low[u]>dfn[v])low[u]=dfn[v];
}
}
if(dfn[u]==low[u])
{
scc++;
do
{
v=Stack[--top];
instack[v]=false;
belong[v]=scc;
}while(v!=u);
}
}
void solve()
{
for(int i=1;i<=n;i++)
if(!dfn[i])tarjan(i);
for(int u=1;u<=n;u++)
{
for(int i=head[u];~i;i=e[i].next)
{
int v=e[i].v;
if(belong[u]!=belong[v])
{
du[belong[u]]++;du[belong[v]]++;
}
}
}
int sum=0;
for(int i=1;i<=scc;i++)
if(du[i]/2==1)sum++;//因为无向图每条边都有正反两个方向，因此所有的点的度都增加了一倍
printf("%d\n",(sum+1)/2);
}
int main()
{
int m,u,v;
while(scanf("%d%d",&n,&m)>0)
{
init();
for(int i=1;i<=m;i++)
{
scanf("%d%d",&u,&v);
addedge(u,v);
addedge(v,u);
}
solve();
}
}