2853076_wa.cpp

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

#include <stdio.h>
#include <algorithm>

using namespace std;

int n;
int adj[27][27];
int din[27], dout[27];
int visited[27], mark[27];
struct node
{
	int len;
	char str[21];
}name[1001];

bool cmp(node a,node b)
{
	return strcmp(a.str,b.str)<0;
}

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 f1, f2, flag;
	int t, i, j, len, tt;
	int st, ed;
	int start, cnt;

	scanf("%d",&t);
	while(t--)
	{
		scanf("%d",&n);
		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));
		for (i = 0; i < n; i++)
		{
			scanf("%s",name[i].str);
			name[i].len = len = strlen(name[i].str);
			adj[name[i].str[0]-'a'][name[i].str[len-1]-'a'] = 1;
			adj[name[i].str[len-1]-'a'][name[i].str[0]-'a'] = 1;
			dout[name[i].str[0]-'a']++;
			din[name[i].str[len-1]-'a']++;
			mark[name[i].str[0]-'a'] = mark[name[i].str[len-1]-'a'] = 1;
		}
		dfs(name[n-1].str[0]-'a');
		tt = 0;
		for (i = 0; i < 26; i++)
		{
			if(mark[i]&&!visited[i])
			{
				printf("***\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)
					ed = i,f1 = 0;
				if(din[i]-dout[i]==-1)
					st = i,f2 = 0;
			}
		}
		if(flag||(!f1&&!f2&&tt==2))
		{
			sort(name,name+n,cmp);
			memset(mark,-1,sizeof(mark));
			for(i = 0; i < n; i++)
			{
				j = i;
				mark[name[i].str[0]-'a'] = i;
				while(j<n&&name[j].str[0]==name[i].str[0])
					j++;
				i = j-1;
			}
			cnt = 0;
			if(flag)
				start = 0;
			else
				start = mark[st];
			int sp;
			char last[21];
			sp = 0;
			while(cnt<n)
			{
				if(!flag&&sp&&cnt==n-1)
				{
					puts(last);				
					break;
				}
				if(!flag&&din[ed]==1&&cnt!=n-1&&!sp&&name[start].str[name[start].len-1]-'a'==ed)
				{
					strcpy(last,name[start].str);
					mark[name[start++].str[0]-'a']++;
					sp = 1;
				}
				printf("%s",name[start].str);
				mark[name[start].str[0]-'a']++;
				if(!flag&&name[start].str[name[start].len-1]-'a'==ed)
					din[ed]--;
				start = mark[name[start].str[name[start].len-1]-'a'];
				cnt++;
				if(cnt==n)
					printf("\n");
				else
					printf(".");
			}
		}
		else
			puts("***");
con:
		;
	}
	return 0;
}