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;}