2700565_ac_234ms_76k.c

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

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

int m;
int adj[27][27];
int din[27], dout[27];
int visited[27];

void dfs(int v)
{
	int i;

	visited[v] = 1;
	for (i = 0; i < 26; i++)
	{
		if(adj[v][i]&&!visited[i])
			dfs(i);
	}
}

int main()
{
	int n, i;
	int flag, len, mark[27];
	int f1, f2, tt;
	char tmp[1001];

	scanf("%d",&n);
	while (n--)
	{
		scanf("%d",&m);
		memset(adj,0,sizeof(adj));
		memset(din,0,sizeof(din));
		memset(dout,0,sizeof(dout));
		memset(mark,0,sizeof(mark));
		memset(visited,0,sizeof(visited));
		tt = 0;
		for (i = 0; i < m; i++)
		{
			scanf("%s",tmp);
			len = strlen(tmp);
			adj[tmp[0]-'a'][tmp[len-1]-'a'] = 1;
			adj[tmp[len-1]-'a'][tmp[0]-'a'] = 1;
			dout[tmp[0]-'a']++;
			din[tmp[len-1]-'a']++;
			mark[tmp[0]-'a'] = mark[tmp[len-1]-'a'] = 1;
		}
		dfs(tmp[0]-'a');
		for (i = 0; i < 27; i++)
		{
			if(mark[i]&&!visited[i])
			{
				printf("The door cannot be opened.\n");
				goto con;
			}
		}
		for(i = 0; i < 27; i++)
		{
			if(mark[i])
			{
				if(din[i]==dout[i])
					mark[i]=0;
			}
		}
		flag = f1 = f2 = 1;
		for (i = 0; i < 27; i++)
		{
			if(mark[i])
			{
				flag = 0;
				tt++;
				if(din[i]-dout[i]==1)
					f1 = 0;
				if(din[i]-dout[i]==-1)
					f2 = 0;
			}
		}
		if(flag||(!f1&&!f2&&tt==2))
			printf("Ordering is possible.\n");
		else
			printf("The door cannot be opened.\n");
con:
		;
	}
	return 0;
}