[POJ 3352] and [POJ 3177]

两题几乎是一样的，除了数据范围有些许差异。题目大意是，有一个连通的无向图，求至少需要添加多少条边，才能使得在图中任意移去一条边后仍然连通。

（又）WA了一天后发现：可以先缩点，将图转换成一颗树，然后求树上叶子结点的数目cnt，如果cnt==1输出0，否则需要增加的边数即为(cnt+1)/2。另外由于是无向图，不需要用入栈标记数组来判横向边，且已知图是连通的，DFS调用一次即可，略为简化了些代码。

具体实现如下：

#include<cstdio>
#include<cstring>

int n,r,el,eel,hd[5001],hde[5001],b[5001],cnt,f[5001];
int st[5001],sl;

struct edge
{
	int i,j,p;
}e[20000],ee[20000];

inline void adde(int i,int j)
{
	e[el].i=i; e[el].j=j; e[el].p=hd[i]; hd[i]=el++;
	e[el].i=j; e[el].j=i; e[el].p=hd[j]; hd[j]=el++;
}

inline void addee(int i,int j)
{
	ee[eel].j=j; ee[eel].p=hde[i]; hde[i]=eel++;
	ee[eel].j=i; ee[eel].p=hde[j]; hde[j]=eel++;
}

int fi(int i)
{
	if(f[i]<0) return i;
	else return f[i]=fi(f[i]);
}

inline void un(int a,int b)
{
	int fa=fi(a),fb=fi(b);
	if(fa==fb) return;
	int na=f[fa],nb=f[fb];
	if(na<nb)
	{
		f[fa]+=nb;
		f[fb]=fa;
	}
	else
	{
		f[fb]+=na;
		f[fa]=fb;
	}
}

void DFS(int i,int f,int d)
{
	int j,k,l;
	b[i]=d;
	st[sl++]=i;
	for(l=hd[i];l!=-1;l=e[l].p)
	{
		j=e[l].j;
		if(!b[j])
		{
			DFS(j,i,d+1);
			b[i]=b[j]<b[i]?b[j]:b[i];
		}
		else if(j!=f) b[i]=b[j]<b[i]?b[j]:b[i];
	}
	if(b[i]==d)
	{
		while(st[--sl]!=i)
		{
			un(i,st[sl]);
		}
	}
}

void DFSe(int i,int f,int d)
{
	int j,k=0,l;
	b[i]=d;
	for(l=hde[i];l!=-1;l=ee[l].p)
	{
		j=ee[l].j;
		if(!b[j])
		{
			DFSe(j,i,d+1);
			b[i]=b[j]<b[i]?b[j]:b[i];
			if(!f)
			{
				if(l!=hde[i]) k=1;
			}
			else if(d<=b[j]) k=1;
		}
		else if(j!=f) b[i]=b[j]<b[i]?b[j]:b[i];
	}
	if(!k) cnt++;
}

int main()
{
	int i,j,k,l;
	while(~scanf("%d%d",&n,&r))
	{
		el=eel=0;
		cnt=0;
		memset(hd,-1,sizeof hd);
		memset(hde,-1,sizeof hde);
		memset(f,-1,sizeof f);
		while(r--)
		{
			scanf("%d%d",&i,&j);
			adde(i,j);
		}
		memset(b,0,sizeof b);
		sl=0;
		DFS(1,0,1);
		for(--el;el>-1;el-=2)
		{
			i=fi(e[el].i); j=fi(e[el].j);
			if(i!=j) addee(i,j);
		}
		memset(b,0,sizeof b);
		DFSe(fi(1),0,1);
		if(cnt<2)
		{
			puts("0");
			continue;
		}
		printf("%d\n",cnt+1>>1);
	}
	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

#include<cstdio>

#include<cstring>

int n,r,el,eel,hd[5001],hde[5001],b[5001],cnt,f[5001];

int st[5001],sl;

struct edge

{

int i,j,p;

}e[20000],ee[20000];

inline void adde(int i,int j)

{

e[el].i=i; e[el].j=j; e[el].p=hd[i]; hd[i]=el++;

e[el].i=j; e[el].j=i; e[el].p=hd[j]; hd[j]=el++;

}

inline void addee(int i,int j)

{

ee[eel].j=j; ee[eel].p=hde[i]; hde[i]=eel++;

ee[eel].j=i; ee[eel].p=hde[j]; hde[j]=eel++;

}

int fi(int i)

{

if(f[i]<0) return i;

else return f[i]=fi(f[i]);

}

inline void un(int a,int b)

{

int fa=fi(a),fb=fi(b);

if(fa==fb) return;

int na=f[fa],nb=f[fb];

if(na<nb)

{

f[fa]+=nb;

f[fb]=fa;

}

else

{

f[fb]+=na;

f[fa]=fb;

}

void DFS(int i,int f,int d)

{

int j,k,l;

b[i]=d;

st[sl++]=i;

for(l=hd[i];l!=-1;l=e[l].p)

{

j=e[l].j;

if(!b[j])

{

DFS(j,i,d+1);

b[i]=b[j]<b[i]?b[j]:b[i];

}

else if(j!=f) b[i]=b[j]<b[i]?b[j]:b[i];

}

if(b[i]==d)

{

while(st[--sl]!=i)

{

un(i,st[sl]);

}

void DFSe(int i,int f,int d)

{

int j,k=0,l;

b[i]=d;

for(l=hde[i];l!=-1;l=ee[l].p)

{

j=ee[l].j;

if(!b[j])

{

DFSe(j,i,d+1);

b[i]=b[j]<b[i]?b[j]:b[i];

if(!f)

{

if(l!=hde[i]) k=1;

}

else if(d<=b[j]) k=1;

}

else if(j!=f) b[i]=b[j]<b[i]?b[j]:b[i];

}

if(!k) cnt++;

}

int main()

{

int i,j,k,l;

while(~scanf("%d%d",&n,&r))

{

el=eel=0;

cnt=0;

memset(hd,-1,sizeof hd);

memset(hde,-1,sizeof hde);

memset(f,-1,sizeof f);

while(r--)

{

scanf("%d%d",&i,&j);

adde(i,j);

}

memset(b,0,sizeof b);

sl=0;

DFS(1,0,1);

for(--el;el>-1;el-=2)

{

i=fi(e[el].i); j=fi(e[el].j);

if(i!=j) addee(i,j);

}

memset(b,0,sizeof b);

DFSe(fi(1),0,1);

if(cnt<2)

{

puts("0");

continue;

}

printf("%d\n",cnt+1>>1);

}

return 0;

}