Catenyms poj hoj 欧拉回路输出路径
#include <stdio.h>#include <cstring>#include <iostream>#include <algorithm>using namespace std;const int maxn=1001;struct edge{ int to,next;} e[10005];struct word{ char s[25];} word[maxn];bool vis[maxn],used[27];int head[maxn],in[27],out[27],f[27];char ans[maxn][30];int n,top,t;void add(int i,int j){ e[t].to=j; e[t].next=head[i]; head[i]=t++;}int cmp(struct word a,struct word b){ return strcmp(a.s,b.s)>=0;}int find(int x){ if(x!=f[x]) f[x]=find(f[x]); return f[x];}void un(int x,int y){ x=find(x); y=find(y); if(x==y) return ; f[y]=x;}int judge(){ int num=0,cnt1=0,cnt2=0,id=-1; for(int i=0; i<26; i++) { if(!used[i]) continue; if(find(i)==i) num++; if(in[i]!=out[i]) { if(in[i]==out[i]+1) cnt1++; else if(out[i]==in[i]+1) cnt2++,id=i; else return -1; } } if(num!=1) return -1; if(!((cnt1==1&&cnt2==1)||(cnt1==0&&cnt2==0))) return -1; if(id==-1) { for(int i=0; i<26; i++) if(out[i]>0) { id=i; break; } } return id;}void eular(int u,int id){ for(int i=head[u]; i!=-1; i=e[i].next) { int v=e[i].to; if(!vis[i]) { vis[i]=true; eular(v,i); } } if(id!=-1) strcpy(ans[top++],word[id].s);}int main(){ int test; scanf("%d",&test); while(test--) { scanf("%d",&n); t=0; memset(head,-1,sizeof(head)); memset(ans,0,sizeof(ans)); memset(in,0,sizeof(in)); memset(out,0,sizeof(out)); memset(used,false,sizeof(used)); memset(vis,false,sizeof(vis)); for(int i=0; i<=27; i++) f[i]=i; for(int i=0; i<n; i++) scanf("%s",word[i].s); sort(word,word+n,cmp); for(int i=0; i<n; i++) { int x=word[i].s[0]-'a'; int y=word[i].s[strlen(word[i].s)-1]-'a'; add(x,y); un(x,y); in[y]++; out[x]++; used[x]=used[y]=true; } int s=judge(); if(s==-1) printf("***\n"); else { top=0; eular(s,-1); for(int i=top-1; i>=0; i--) { printf("%s",ans[i]); if(i!=0) printf("."); } printf("\n"); } } return 0;}