<题目链接>
<转载于 >>> >
题目大意：
有n个牧场，Bessie 要从一个牧场到另一个牧场，要求至少要有2条独立的路可以走。现已有m条路，求至少要新建多少条路，使得任何两个牧场之间至少有两条独立的路。两条独立的路是指：没有公共边的路，但可以经过同一个中间顶点。
解题分析：
在同一个边双连通分量中，任意两点都有至少两条独立路可达，所以同一个边双连通分量里的所有点可以看做同一个点。
缩点后，新图是一棵树，树的边就是原无向图的桥。
现在问题转化为：在树中至少添加多少条边能使图变为双连通图。
结论：添加边数=（树中度为1的节点数+1）/2
具体方法为，首先把两个最近公共祖先最远的两个叶节点之间连接一条边，这样可以把这两个点到祖先的路径上所有点收缩到一起，因为一个形成的环一定是双连通的。然后再找两个最近公共祖先最远的两个叶节点，这样一对一对找完，恰好是(leaf+1)/2次，把所有点收缩到了一起。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std; const int N = 5e3+ , M = 1e4+;
#define clr(a,b) memset(a,b,sizeof(a))
struct Edge{
int to,next;
}edge[M<<]; int head[N],low[N],dfn[N],belong[N],deg[N],stk[N],instk[N];
int n,m,tot,cnt,top,scc;
void addEdge(int u,int v){
edge[tot].to=v,edge[tot].next=head[u];
head[u]=tot++;
}
void init(){
tot=cnt=top=scc=;
clr(head,-);clr(low,);clr(dfn,);clr(instk,);clr(deg,);
}
void Tarjan(int u,int fa){
low[u]=dfn[u]=++cnt;
stk[++top]=u;instk[u]=;
for(int i=head[u];~i;i=edge[i].next){
int v=edge[i].to;
if(i==(fa^))continue; //不能用搜索树上的边来更新low值，这种写法能够用来处理重边的情况
if(!dfn[v]){
Tarjan(v,i);
low[u]=min(low[u],low[v]);
}
else if(instk[v]) //此时栈里的所有元素均属于同一边双连通分量,找连通分量的根的时候一定要规定这点，否则可能会与其他连通分量的dfn比较
low[u]=min(low[u],dfn[v]); //low值全部等于该双连通分量中最先遍历的点dfn值
}
if(dfn[u]==low[u]){
++scc;
while(true){
int v=stk[top--];
instk[v]=;
belong[v]=scc; //将该联通块中的所有点全部缩点染色
if(v==u)break;
}
}
}
int main(){
while(scanf("%d%d",&n,&m)!=EOF){
init();
for(int i=;i<=m;i++){
int u,v;scanf("%d%d",&u,&v);
addEdge(u,v),addEdge(v,u);
}
Tarjan(,-);
for(int i=;i<=n;i++){
for(int j=head[i];j!=-;j=edge[j].next){
int v=edge[j].to;
if(belong[i]!=belong[v])
deg[belong[i]]++; //求出缩点后每个点的度
}
}
int sum=;
for(int i=;i<=scc;i++)if(deg[i]==)sum++; //寻找度为1的叶子节点
int ans=(sum+)/;
printf("%d\n",ans);
}
}
2018-11-07