Jennie

每个单词只有两个字符，那么就在这两个字符之间连一条边。

最后n+1个字符，显然是所有单词只出现了一遍

这样我们的目标就是找一条欧拉路径就可以了

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n;
string s;
int du[100001];
int fa[1000001];
int find(int x){
    return x==fa[x]?x:find(fa[x]);
}
int ed[1005][1005];
int ans[100001];
void dfs(int x){
    for(int i=0;i<='z'-'A';++i){
        if(ed[x][i]){
            ed[x][i]=ed[i][x]=0;
            dfs(i);
        }
    }
    ans[n--]=x;
}
int main(){
    scanf("%d",&n);
    for(int i='a'-'a';i<='z'-'A';++i){
        fa[i]=i;
    }
    for(int i=1;i<=n;++i){
        cin>>s;
        ed[s[0]-'A'][s[1]-'A']=ed[s[1]-'A'][s[0]-'A']=1;
        du[s[0]-'A']++;
        du[s[1]-'A']++;
        fa[find(fa[s[0]-'A'])]=find(fa[s[1]-'A']);
    }
    int cnt=0;
    for(int i='a'-'a';i<='z'-'A';++i){
        if(du[i]&&fa[i]==i){
            cnt++;
        }
    }
    if(cnt!=1){
        cout<<"No Solution";
        return 0;
    }
    cnt=0;
    for(int i=0;i<='z'-'A';++i){
        if(du[i]&&du[i]%2){
            cnt++;
        }
    }
    int tem=n;
    if(cnt!=0&&cnt!=2){
        cout<<"No Solution";
        return 0;
    }
    int st;
    for(int i=0;i<='z'-'A';++i){
        if(cnt==2){
            if(du[i]%2){
                st=i;
                break;
            }
        }else{
            if(du[i]){
                st=i;
                break;
            }
        }
    }
    dfs(st);
    for(int i=0;i<=tem;++i){
        cout<<char(ans[i]+'A');
    }
    return 0;
}