poj3177——Redundant Paths//最小割边

跟3352一模一样，不过，需加判重。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,r;
#define maxn 5005
bool map[maxn][maxn];
class node
{
public:
	int to,next;
};
node g[maxn*5];
int head[maxn],cnt;
int dfn[maxn],low[maxn],du[maxn];
void add(int u,int v)
{
	g[++cnt].to =v;
	g[cnt].next =head[u];
	head[u]=cnt;
}
void dfs(int u,int fa)
{
	dfn[u]=low[u]=++cnt;
	int i;
	for(i=head[u];i;i=g[i].next )
	{
		int v=g[i].to;
		if(!dfn[v])
		{
			dfs(v,u);
			low[u]=min(low[u],low[v]);
		}
		else if(v!=fa)
		{
			low[u]=min(low[u],dfn[v]);
		}
	}
}
void solve()
{
	int i,j,ans=0;
	memset(dfn,0,sizeof(dfn));
	memset(low,0,sizeof(low));
	cnt=0;
	dfs(1,-1);
	memset(du,0,sizeof(du));
	for(i=1;i<=n;i++)
	{
		for(j=head[i];j;j=g[j].next )
		{
			int v=g[j].to;
			if(low[i]!=low[v]) du[low[i]]++;//low值相同的节点即在一个双联通分量里
		}
	}
	for(i=1;i<=n;i++)
	{
	//	printf("%d ",du[i]);
		if(du[i]==1)ans++;
	}
	//printf("\n");
//	for(i=1;i<=n;i++)
	//	printf("%d ",low[i]);
	//printf("\n");
	printf("%d\n",(ans+1)/2);
}
int main()
{
	int a,b;
	while(scanf("%d%d",&n,&r)!=EOF)
	{
		cnt=0;
		memset(map,0,sizeof(map));
		while(r--)
		{
			scanf("%d%d",&a,&b);
			if(!map[a][b])
			{
				add(a,b);
		    	add(b,a);
				map[a][b]=map[b][a]=1;
			}
		}
		solve();
	}
	return 0;
}