2431927_wa.cc

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int n, e;
int map[101][101];
int visited[101];
int stack[101], flag[101];
int cycle, ans, cat;

void dfs(int pre,int v,int l)
{
	int i, j, mark = 0;

	visited[v] = flag[v] = 1;
	for(i = 0; i < n; i++)
	{
		if(cycle||cat)
			return ;
		if(map[v][i])
		{
			if(!visited[i])
			{
				mark = 1;
				stack[l] = i;
				dfs(v,i,l+1);
			}
			else
				if(i!=pre)
				{
					cycle = true;
					return ;
				}
		}
	}
	ans = 0;
	if(!mark)
	{
		//system("pause");
		stack[l++] = v;
		for(i = 0; i < l; i++)
		{
			for(j = 0; j < n; j++)
				if(map[stack[i]][j]&&!flag[j])
					ans++;
		}
		//printf("%d %d\n",l+1,ans);
		if(ans+l==n)
			cat = true;

	}
	flag[v] = 0;
}

int main()
{
	int i, cas = 0;
	int a, b;

	while(scanf("%d",&n)==1&&n)
	{
		++cas;
		memset(map,0,sizeof(map));
		memset(flag,0,sizeof(flag));
		memset(visited,0,sizeof(visited));
		scanf("%d",&e);
		cycle = cat = false;
		for(i = 0; i < e; i++)
		{
			scanf("%d%d",&a,&b);
			a--,b--;
			map[a][b] = map[b][a] = 1;
		}
		dfs(-1,0,0);
		if(cat)
			printf("Graph %d is a caterpillar.\n",cas);
		else
			printf("Graph %d is not a caterpillar.\n",cas);
	}
	return 1;
}