2552592_ac_46ms_80k.c

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

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <stdlib.h>

int map[21][21];
int m, n, mark;

int sum()
{
	int i, j, s;

	s = 0;
	for(i = 0; i < n; i++)
		for(j = 0; j < n; j++)
			s += map[i][j];
	return s;
}

void dfs(int v)
{
	int i;
	int m;

	m = 1;
	for(i = 0; i < n; i++)
		if(map[v][i])
		{
			m = 0;
			map[v][i]--;map[i][v]--;
			dfs(i);
			map[v][i]++;map[i][v]++;
		}
	if(m&&v==0&&!sum())
		mark = 1;
}

int main()
{
	char tmp[100];
	int j, i, ans;

	while(scanf("%s",tmp)==1&&tmp[0]!='E')
	{
		scanf("%d%d",&m,&n);
		getchar();
		mark = ans = 0;
		memset(map,0,sizeof(map));
		for(i = 0; i < n; i++)
		{
			gets(tmp);
			for(j = 0; tmp[j]!= '\0'; j++)
			{
				if(isdigit(tmp[j]))
				{
					ans++;
					map[i][atoi(&tmp[j])]++;map[atoi(&tmp[j])][i]++;
					while(tmp[j]!='\0'&&isdigit(tmp[j]))
						j++;
					if(tmp[j]=='\0')
						break;
				}
			}
		}
		gets(tmp);
		dfs(m);
		if(mark)
			printf("YES %d\n",ans);
		else
			printf("NO\n");
	}
	return 0;
}