学步园

来源：http://poj.org/problem?id=3177

题意：给一个图，求最少需要添加几条边才能使任意两个点之间有至少两条路径。路径是不包括重边的，比如1 2 和2 1是一条路。

思路：其实就是一个求割边然后缩点，缩点之后求度为1的点即可。我写的这道题其实是有bug了，只不过这道题数据水了才过了，正常情况下是过不了的。统计度为1的时候不知道怎么能够消除重边的影响。附有bug的代码：

#include <iostream>
#include <cstdio>
#include <string.h>
#include <vector>
using namespace std;

#define CLR(arr,val) memset(arr,val,sizeof(arr))
const int N = 5010;
vector<int> vv[N];
int low[N],dfn[N],vis[N],numblock[N],head[N],instack[N],degree[N],use[1010][1010];
int timeorder,numpoint,numroad,numedge,numss,numcnt;
struct edge{
	int lp,rp,next;
}ee[N*2];
void init(){
	CLR(low,0);
	CLR(dfn,0);
	CLR(vis,0);
	CLR(degree,0);
	CLR(head,-1);
	CLR(numblock,0);
	timeorder = 0;
	numedge = 0;
	numss = 0;
	numcnt = 0;
}
void add_edge(int x,int y){
	ee[numedge].lp = x;
	ee[numedge].rp = y;
	ee[numedge].next = head[x];
	head[x] = numedge++;
}
void dfs(int x,int fa){
	timeorder++;
	low[x] = dfn[x] = timeorder;
	vis[x] = 1;
	numss++;
	instack[numss] = x;
	for(int i = head[x]; i != -1; i = ee[i].next){
	   int y = ee[i].rp;
	   if(y == fa)continue;
	   if(!vis[y]){
	      dfs(y,x);
		  low[x] = min(low[x],low[y]);
		  if(low[y] > dfn[x]){
		    numcnt++;
			while(1){
			  int tt = instack[numss];
			  numblock[tt] = numcnt;
			  if(instack[numss--] == y)
				  break;
			}
		  }
	   }
	   else
		   low[x] = min(low[x],dfn[y]);
	}
}
int main(){
	//freopen("1.txt","r",stdin);
	while(scanf("%d%d",&numpoint,&numroad) != EOF){
	    init();
		int x,y;
		while(numroad--){
		   scanf("%d%d",&x,&y);
           add_edge(x,y);
		   add_edge(y,x);
		}
		dfs(1,1);
		bool flag = false;
		while(numss){
			flag = true;
		   int tt = instack[numss--];
		   numblock[tt] = numcnt+1;
		}
		if(flag) numcnt++;
		CLR(use,0);
		for(int i = 0; i < numedge; i += 2){
		   int x = ee[i].lp;
		   int y = ee[i].rp;
		   if(use[x][y])continue;
		   use[x][y] = use[y][x] = 1;
		   if(numblock[x] != numblock[y]){
		      degree[numblock[x]]++;
			  degree[numblock[y]]++;
		   }
		}
		int ans = 0;
		if(numcnt == 1){
		  printf("0\n");
		  continue;
		}
		for(int i = 1; i <= numcnt; ++i)
			if(degree[i] == 1)
				ans++;
		printf("%d\n",(ans+1)/2);
	}
	return 0;
}