catenyms(欧拉路，输出路径).cpp

杭电acm解题报告2001---2099.

#include <cstdio>
#include <string>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;

const int MAX = 1100;
char str[MAX][25];
int n, in[MAX], out[MAX];
vector<string> words[30];
int vis[30];
int f[30], ss, is, os, ps;

int seq[MAX], step;
void find_euler(int pos) 
{
	int i,j;
	while(out[pos]) {
		for(; vis[pos] < words[pos].size() ;) {
			string snext = words[pos][ vis[pos] ];
			j = snext[snext.length() -1] -'a';
			out[pos] --;
			vis[pos] ++;
			find_euler(j);
		}
	}
	seq[step ++] = pos;
}

void union_f(int s,int e)
{
	int ts = s, te = e;
	while(s != -1 && f[s] != s) {
		s = f[s];
	}
	if(s == -1) {
		f[ts] = s = ts;
	}
	while(e != -1 && f[e] != e) {
		int t = e;
		e = f[e];
		f[t] = s;
	}
	if(e >= 0) {
		f[e] = s;
	}
}

int main()
{
	int t,i,j;
	scanf("%d", &t);
	while(t --) {
		scanf("%d", &n);
		getchar();
		for(i=0;i<30;i++) words[i].clear();
		memset(in,0,sizeof(in));
		memset(out,0,sizeof(out));
		memset(f,-1,sizeof(f));
		ss = is = os = ps = 0;
		for(i=0;i<n;i++) {
			gets(str[i]);
			int len = strlen(str[i]);
			int chs = str[i][0] -'a';
			int che = str[i][len-1] -'a';
			words[chs].push_back(string(str[i]));
			in[che] ++;
			out[chs] ++;
			union_f(chs, che);
		}
		bool flag = true;
		for(i=0;i<30;i++) {
			if(f[i] == i) ss ++;
			if(in[i] == out[i] +1) os ++;
			else if(in[i] +1 == out[i]) is ++;
			else if(in[i] != out[i]) flag = false;
		}
		if(ss > 1) flag = false;
		if( !(os==0 && is==0) && !(os==1 && is==1) ) flag = false;
		if(!flag) {
			puts("***");
		}
		else {
			int spos;
			if(os == 1 && is == 1) {
				for(i=0;i<30;i++) {
					if(in[i] +1 == out[i]) {
						spos = i;
						break;
					}
				}
			}
			else {
				for(i=0;i<30;i++) {
					if(f[i] != -1) {
						spos = i;
						break;
					}
				}
			}
			for(i=0;i<30;i++) sort(words[i].begin(), words[i].end());
			step = 0;
			memset(vis, 0, sizeof(vis));
			find_euler(spos);
			for(i=step-1;i>0;i--) {
				spos = seq[i];
				string snext;
				for(j=0;j<words[spos].size();j++) {
					snext = words[spos][j];
					if(seq[i-1] == snext[snext.length() -1] -'a') {
						words[spos].erase(words[spos].begin() +j);
						break;
					}
				}
				printf("%s", snext.c_str());
				if(i>1) putchar('.');
			}
			puts("");
		}
	}
}