poj 3177 Redundant Paths 边双连通

出自http://blog.csdn.net/wangjian8006/article/details/7990666#

#include <iostream>
using namespace std;
#define MAXV 5010
#define min(a,b) (a>b?b:a)

int n,m;
bool map[MAXV][MAXV];
bool vis[MAXV];
int low[MAXV],dfn[MAXV];
int count;
int cnt[MAXV];

void init(){
	memset(vis,0,sizeof(vis));
	memset(low,0,sizeof(low));
	memset(dfn,0,sizeof(dfn));
	count=0;
}

void dfs(int x,int pre){
	int i;
	vis[x]=1;
	low[x]=dfn[x]=++count;
	for(i=1;i<=n;i++){
		if(map[x][i]){
			if(!vis[i]){
				dfs(i,x);
				low[x]=min(low[x],low[i]);
			}
			if(vis[i]==1 && i!=pre){
				low[x]=min(low[x],dfn[i]);
			}
		}
	}
}

int main(){
	int a,b;
	int i,j;
	while(~scanf("%d%d",&n,&m)){
		memset(map,0,sizeof(map));
		while(m--){
			scanf("%d%d",&a,&b);
			map[a][b]=map[b][a]=1;
		}

		init();
		dfs(1,1);

		memset(cnt,0,sizeof(cnt));	
		for(i=1;i<=n;i++){					//计算每个点的度
			for(j=1;j<=n;j++)
				if(map[i][j]){
					if(low[i]!=low[j]){
						cnt[low[j]]++;
					}
				}
		}
		int ans=0;				//计算度为1的点的个数
		for(i=1;i<=n;i++){
			if(cnt[i]==1) ans++;
		}
		printf("%d
",(ans+1)/2);
	}
	return 0;
}