学步园

题意：给你n个单词，让每个单词的最后一个字母恰好等于下一个单词的第一个字母。构造这样一个串，使每个单词恰好被用到一次。取字典序最小的。

例如，把 aloha     arachnid    dog   gopher    rat    tiger  串成 aloha.arachnid.dog.gopher.rat.tiger。 若所个的单词不能构成这样一个串，那么输出“***”。

题解：乍一看像哈密顿图，但其实只要把每个单词当做一条边，就可以用欧拉图来做。首先对所有的单词按字典序排一下，其实也就是将所有的边排下序，以保证字典序最小。当然，如果采用头插法构图，只需要每次插入边的时候冒泡一下也可以保证字典序。还有两点需要注意：1.验证图的连通性；2.如果是欧拉图，则从字典序最小的边的起点开始搜索，如果是半欧拉图，一定要从出度大于入度的那条边开始搜索。

#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;

struct Word { int l; char s[21]; };
struct Edge { int st, ed; bool del; };

Word word[1002];
Edge edge[1002];
int in[30], out[30];
int stk[1002], father[30];
bool mark[30];
int E, top;

int cmp ( const void* a, const void* b )
{
	return strcmp( ((Word*)a)->s, ((Word*)b)->s );
}

int find_set ( int x )
{
	if ( father[x] != x )
		father[x] = find_set ( father[x] );
	return father[x];
}

bool judge ()
{
	int t = 0;
	for ( int i = 0; i < 26; i++ )
		if ( mark[i] && father[i] == i ) t++;
	return t == 1;
}

void find_path ( int u )
{
	for ( int i = 0; i < E; i++ )
	{
		if ( ! edge[i].del && edge[i].st == u )
		{
			edge[i].del = true;
			find_path ( edge[i].ed );
			stk[top++] = i;
		}
	}
}

int main()
{
	int cs;
	scanf("%d",&cs);
	while ( cs-- )
	{
		scanf("%d",&E);
		int u, v, c1, c2, start, i;

		for ( i = 0; i < 26; i++ )
		{
			in[i] = out[i] = 0;
			father[i] = i;
			mark[i] = false;
		}

		for ( i = 0; i < E; i++ )
		{
			scanf("%s",word[i].s);
			word[i].l = strlen(word[i].s);
		}

		qsort(word, E, sizeof(word[0]), cmp);
		
		for ( i = 0; i < E; i++ )
		{
			u = word[i].s[0] - 'a';
			v = word[i].s[word[i].l-1] - 'a';
			edge[i].st = u;
			edge[i].ed = v;
			edge[i].del = false;
			mark[u] = mark[v] = true;
			out[u]++; in[v]++;
			u = find_set ( u );
			v = find_set ( v );
			if ( u != v ) father[v] = u;
		}

		c1 = c2 = 0;
		start = edge[0].st;
		for ( i = 0; i < 26; i++ )
		{
			if ( in[i] == out[i] ) continue;
			else if ( in[i] - 1 == out[i] ) c1++;
			else if ( out[i] - 1 == in[i] ) { c2++; start = i; }
			else break;
		}

		if ( i == 26 && ((c1 == c2 && c1 == 1) || (c1 == c2 && c1 == 0)) && judge() )
		{
			top = 0;
			find_path ( start );
			for ( i = top - 1; i > 0; i-- )
				printf("%s.",word[stk[i]].s);
			printf("%s\n",word[stk[0]].s);
		}
		else printf("***\n");
	}
	//system("pause");
	return 0;
}