2570900_ac_0ms_236k.cpp

来自「北大大牛代码 1240道题的原代码 超级权威」· C++ 代码 · 共 78 行

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

char v[200];
int map[200][200];
int d, dd[200];
int visited[200];
int flag, start, mark[200];

void dfs(int v)
{
	int i;

	visited[v] = 1;
	for(i = 0; i < d; i++)
		if(map[v][i]&&!visited[i])
			dfs(i);
}

int conected()
{
	int i;

	memset(visited,0,sizeof(visited));
	dfs(start);
	for(i = 0; i < d; i++)
		if(!visited[i]&&mark[i])
			return 0;
	return 1;
}

int main()
{
	int i;
	char tmp[10000], ch, ci;

	while(gets(tmp)!=NULL)
	{
		d = 'z'+1;flag = 0;
		memset(mark,0,sizeof(mark));
		memset(map,0,sizeof(map));
		memset(dd,0,sizeof(dd));
		i = 0;
		while(1)
		{
			for(; tmp[i]!='('&&tmp[i]!='\0'; i++);
			if(tmp[i]=='\0')
				break;
			i++;
			ch = tmp[i];
			start = ch;
			ci = tmp[i+2];
			mark[ch] = mark[ci] = 1;
			map[ch][ci] = map[ci][ch] = 1;
			dd[ch]++,dd[ci]++;
		}
		if(!conected())
		{
			printf("No No\n");
			continue;
		}
		else
		{
			int	num = 0;
			for(i = 0; i < d; i++)
				if(dd[i]%2)
					num++;
			if(num==2)
				printf("Yes No\n");
			else
				if(num==0)
					printf("No Yes\n");
				else
					printf("No No\n");
		}
	}
	return 0;
}