Solution
找一条字典序最小的欧拉路径。
用 $multiset$ 存储领接表。
Code
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<set>
using namespace std; const int N = 1e3 + ; int n, up = 'z' - 'A' + ;
int ans[N], tot, d[N], num; multiset<int> to[N]; void dfs(int u) {
multiset<int> :: iterator i;
for (i = to[u].begin(); i != to[u].end(); i = to[u].begin()) {
int nt = *i;
to[nt].erase(to[nt].find(u));
to[u].erase(to[u].find(nt));
dfs(nt);
}
ans[++tot] = u;
} int main()
{
scanf("%d", &n);
for (int i = ; i <= n; ++i) {
char s[];
scanf("%s", s);
to[s[] - 'A' + ].insert(s[] - 'A' + );
to[s[] - 'A' + ].insert(s[] - 'A' + );
d[s[] - 'A' + ]++;
d[s[] - 'A' + ]++;
}
for (int i = ; i <= up; ++i)
if (d[i] & )
num++;
if (num == || num > )
return puts("No Solution"), ;
if (num == ) {
for (int i = ; i <= up; ++i)
if (d[i]) {dfs(i); break;}
}
else
for (int i = ; i <= up; ++i)
if (d[i] && (d[i] & )) {dfs(i); break;}
for (int i = tot; i; i--)
putchar(ans[i] + 'A' - );
puts("");
}