题目地址：POJ 2337
这题跟POJ 1386差不多，，只不过这题多一个输出路径而已。
按字母来建边，每个单词的首字母和尾字母加边。先判断是否连通，然后判断每个字母的入度和出度不能出现差的绝对值大于2，然后入度和出度差的绝对值为1的不能超过两个。就可以形成欧拉路径
代码如下：
#include <iostream>#include <string.h>#include <math.h>#include <queue>#include <algorithm>#include <stdlib.h>#include <map>#include <set>#include <stdio.h>using namespace std;#define LL long long#define pi acos(-1.0)const int mod=1e9+7;const int INF=0x3f3f3f3f;const double eqs=1e-9;int head[30], cnt, in[30], out[30], bin[30], path[1100], top, vis[1100], ha[30], c[30];int find1(int x){return bin[x]==x?x:bin[x]=find1(bin[x]);}void join(int x, int y){int f1=find1(bin[x]);int f2=find1(bin[y]);if(f1!=f2){bin[f2]=f1;}}struct N{char s[30];}fei[1100];bool cmp(N f1, N f2){return strcmp(f1.s,f2.s)>0;}struct node{int u, v, id, next;}edge[1100];void add(int u, int v, int id){edge[cnt].v=v;edge[cnt].id=id;edge[cnt].next=head[u];head[u]=cnt++;}void dfs(int u){for(int i=head[u];i!=-1;i=edge[i].next){if(!vis[edge[i].id]){vis[edge[i].id]=1;head[u]=i;dfs(edge[i].v);path[top++]=edge[i].id;}i=head[u];}}void init(){memset(head,-1,sizeof(head));cnt=top=0;memset(vis,0,sizeof(vis));memset(in,0,sizeof(in));memset(out,0,sizeof(out));memset(ha,0,sizeof(ha));}int main(){int t, n, i, j, len, k, sum, flag, x, pos;scanf("%d",&t);while(t–){scanf("%d",&n);init();for(i=0;i<n;i++){scanf("%s",fei[i].s);}sort(fei,fei+n,cmp);k=0;for(i=0;i<26;i++){bin[i]=i;}for(i=0;i<n;i++){len=strlen(fei[i].s);in[fei[i].s[len-1]-'a']++;out[fei[i].s[0]-'a']++;if(!ha[fei[i].s[0]-'a']){ha[fei[i].s[0]-'a']=1;c[k++]=fei[i].s[0]-'a';}if(!ha[fei[i].s[len-1]-'a']){ha[fei[i].s[len-1]-'a']=1;c[k++]=fei[i].s[len-1]-'a';}add(fei[i].s[0]-'a',fei[i].s[len-1]-'a',i);join(fei[i].s[0]-'a',fei[i].s[len-1]-'a');}//printf("k===%d\n",k);sum=flag=0;x=find1(bin[c[0]]);for(i=0;i<k;i++){if(abs(in[c[i]]-out[c[i]])>1) flag=1;if(in[c[i]]!=out[c[i]]) sum++;if(find1(bin[c[i]])!=x) flag=1;}if(flag||sum>2){puts("***");continue ;}sort(c,c+k);pos=c[0];for(i=0;i<k;i++){if(out[c[i]]>in[c[i]]){pos=c[i];break;}}dfs(pos);for(i=top-1;i>=0;i–){printf("%s",fei[path[i]].s);if(i) printf(".");}puts("");}return 0;}
旅行，有一种苍凉，“浮云游子意，落日故人情”，
