poj_3310.txt

poj 3310 的代码和方法说明,个人原创

//此题数据太弱了,所以再差的方法做都可以0ms搞定,个人认为,n至少应该大于10000才能比较出算法的优劣性;
//方法如下:首先判断这个图是否含有n-1条边,如果不是,那么这个图要么不连通 ,要么含有环,或者两种都可能,反正肯定不符合
//题目要求,在此基础上,dfs一次,如果有环或者以某个节点为根的子树含有2个以上超过1个节点,那么就不是caterpillar,就这么简单,
//,时间复杂度为--深搜一棵树的复杂度,代码如下
#include<iostream>
using namespace std;
int cas,n,e,visit[101],total,ind[101],root,inf[101],gra[101][101];
void output(int flag)
{
	printf("Graph %d is ",cas);
	if(flag==0)
	{
		printf("not ");
	}
	printf("a caterpillar.\n");
}
int dfs(int father,int index)
{
	int sum=0,i,p=0,kk;
	for(i=1;i<=ind[index];i++)
	{
		if(visit[gra[index][i]]==0)
		{   visit[gra[index][i]]=1;
		   
			kk=dfs(index,gra[index][i]);
			if(kk==-1)
				return -1;
			sum+=kk+1;
			if(kk+1>=2)
				p++;
		}
		else if(visit[gra[index][i]]&&gra[index][i]!=father)
			return -1;
	}
	if(n-sum-1>=2)
		p++;
	if(p>2)
	return -1;
	return sum;
}
int main()
{
	while(scanf("%d",&n)&&n)
	{
		cin>>e;
		cas++;
	
		memset(visit,0,sizeof(visit));
memset(ind,0,sizeof(ind));
		visit[1]=1;
		root=1;
		int a,b;
		int i,j,k;
		for(i=1;i<=e;i++)
		{	scanf("%d %d",&a,&b);
		   ind[a]++;
		   ind[b]++;
		   gra[a][ind[a]]=b;
		   gra[b][ind[b]]=a;
		}
		bool flag;
	if(e!=n-1||dfs(0,1)!=n-1)
	        flag=0;
          else
			  flag=1;
		  output(flag);
	}
	return 0;
}