买一送一啊 3177和3352的区别在于3177数据有重边！但是我先做3177的 那么就直接ctrl+c+v搞3352了~。
题意：给一个无向图，要令每个点之间至少有两条不重合的路，需要至少加多少条边。
思路：找出无向图中边双联通的点进行缩点后，根据缩点图的每条边（割边）给缩点增加度数，通过图的结构可以得出
公式：至少增加的边数 =（这棵树总度数为1的结点数 + 1 ）/ 2。
事实上求割边的方法可以用Tarjan方法的变形来求得，同时因为是无向图，要记录其父节点pre。可以知道对于边u，v；当Low[u]==Low[v]时，可以确定u，v在同一个边双联通，对于Low值不同，即不再同一个边双联通的点的边进行度的增加，因为无向图，求出degree【】/2==1的个数leaf，最后得出答案。
在discuss里面有人说Low[]值不同并不代表其一定不在同一个边双联通分量中。事实上这个结论在有向图中是对的，但在无向图中，当新的点找到其已经标记过的点时，其Low值会更新为新点更小的DFN值，然后继续遍历一直取到新点连通的最小DFN值，即为该双联通分量的Low值。
代码：
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
#define MAXN 5005
#define MAXM 22000
struct Edge
{
int to,next;
}edge[MAXM];
int first[MAXN],DFN[MAXN],Low[MAXN];
bool map[MAXN][MAXN];
int degree[MAXN];
int cnt,tot,n,m,count; void Tarjan(int v,int pre)
{
DFN[v]=Low[v]=++count;
for(int i=first[v];i!=-1;i=edge[i].next)
{
int j=edge[i].to;
if(j!=pre&&DFN[j]<DFN[v])
{
if(!DFN[j])
{
Tarjan(j,v);
Low[v]=min(Low[j],Low[v]);
}
else
{
Low[v]=min(DFN[j],Low[v]);
}
}
}
}
void addedge(int v,int w)
{
edge[tot].to=w;
edge[tot].next=first[v];
first[v]=tot++;
} int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
memset(first,-1,sizeof(first));
memset(DFN,0,sizeof(DFN));
cnt=tot=0;
memset(Low,0,sizeof(Low));
memset(map,false,sizeof(map));
memset(degree,0,sizeof(degree)); count=0; for(int i=0;i<m;i++)
{
int a,b;
scanf("%d%d",&a,&b);
if(map[a][b]==false)
{
addedge(a,b);
addedge(b,a);
map[a][b]=true;
map[b][a]=true;
}
}
Tarjan(1,1);
for(int i=1;i<=n;i++)
{
for(int j=first[i];j!=-1;j=edge[j].next)
{
int v=edge[j].to;
if(Low[i]!=Low[v])
{
degree[Low[v]]++;
degree[Low[i]]++;
}
}
}
int leaf=0;
for(int i=1;i<=n;i++)
{
cout<<degree[i]<<endl;
if(degree[i]/2==1)
leaf++;
}
printf("%d\n",(leaf+1)/2);
}
return 0;
}