题目链接：
poj3177
题意：
给出一张连通图,为了让任意两点都有两条通路(不能重边,可以重点),至少需要加多少条边
题解思路:
分析：在同一个边双连通分量中，，任意两点都有至少两条独立路可达，所以同一个边双连通分量里的所有点可以看做同一个点。
缩点后，新图是一棵树，树的边就是原无向图桥。
现在问题转化为：在树中至少添加多少条边能使图变为双连通图。
结论：添加边数=（树中度为1的节点数+1）/2
具体方法为，首先把两个最近公共祖先最远的两个叶节点之间连接一条边，这样可以把这两个点到祖先的路径上所有点收缩到一起，因为一个形成的环一定是双连通的。然后再找两个最近公共祖先最远的两个叶节点，这样一对一对找完，恰好是(leaf+1)/2次，把所有点收缩到了一起。
代码:
#include<iostream>#include<cstdio>#include<cstring>#define maxn 5050using namespace std;struct node{int to,tag,next;} edge[maxn*4];int head[maxn];int s;int dfn[maxn],low[maxn],num;int stack[maxn],top;int belong[maxn],block; //连通块void init(){memset(head,-1,sizeof(head));memset(dfn,0,sizeof(dfn));block=num=top=s=0;}void addedge(int a,int b){edge[s]= {b,0,head[a]};head[a]=s++;}void Tarjan(int u,int pre){dfn[u]=low[u]=++num;stack[top++]=u;for(int i=head[u]; i!=-1; i=edge[i].next){int v=edge[i].to;if(!dfn[v]){Tarjan(v,u);low[u]=min(low[u],low[v]);if(dfn[u]<low[v]){edge[i].tag=1;//edge[i^1].tag=1;//标记割边}}else if(pre!=v)low[u]=min(low[u],dfn[v]);}if(low[u]==dfn[u])//找到一个边双连通分量的根节点{int d;block++;while(1){d=stack[–top];belong[d]=block;//缩点 类似并查集的father[]if(d==u)break;}}}int main(){int degree[maxn];int ans;int n,m,a,b;while(~scanf("%d%d",&n,&m)){init();while(m–){scanf("%d%d",&a,&b);addedge(a,b);addedge(b,a);}Tarjan(1,-1);memset(degree,0,sizeof(degree));ans=0;for(int i=1; i<=n; i++)//缩点后 不需要构图 只需要判断顶点度数即可{for(int j=head[i]; j!=-1; j=edge[j].next)if(edge[j].tag==1)//缩点后只有割边才能成为这些"点"的边degree[belong[i]]++;}for(int i=1; i<=block; i++)if(degree[i]==1)ans++;cout<<(ans+1)/2<<endl;}return 0;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
便觉不过如此。也许我们只是想让自己的心去旅行，
