2432505_ac_0ms_100k.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, node;

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

	visited[v] = flag[v] = 1;
	for(i = 0; i < n; i++)
	{
		if(map[v][i])
		{
			if(!visited[i])
			{
				mark = 1;
				stack[l] = i;
				dfs(i,l+1);
			}
		}
	}
	ans = 0;
	if(!mark)
	{
		for(i = 0; i < l; i++)
		{
			for(j = 0; j < n; j++)
				if(map[stack[i]][j]&&!flag[j])
					ans++;
		}
		if(ans+l==n)
			cat = true;

	}
	flag[v] = 0;
}

void Dfs(int pre,int v)
{
	int i;

	visited[v] = 1;
	for(i = 0; i < n; i++)
	{
		if(map[v][i])
			if(!visited[i])
				node++,Dfs(v,i);
			else
				if(i!=pre)
				{
					cycle = true;
					return ;
				}
	}
}

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;node = 1;
		for(i = 0; i < e; i++)
		{
			scanf("%d%d",&a,&b);
			if(a==b)
				continue;
			a--,b--;
			map[a][b] = map[b][a] = 1;
		}
		Dfs(-1,0);
		if(cycle||node!=n)
		{
			printf("Graph %d is not a caterpillar.\n",cas);
			continue;
		}
		memset(visited,0,sizeof(visited));
		stack[0] = 0;
		dfs(0,1);
		if(cat)
			printf("Graph %d is a caterpillar.\n",cas);
		else
			printf("Graph %d is not a caterpillar.\n",cas);
	}
	return 1;
}