题目描述
给定n个各不相同的无序字母对(区分大小写,无序即字母对中的两个字母可以位置颠倒)。请构造一个有n+1个字母的字符串使得每个字母对都在这个字符串中出现。
分析
欧拉回路的模板题。
暴力删边欧拉回路,邻接矩阵实现就可以了。
代码
#include <bits/stdc++.h>
#pragma GCC optimize(2)
#define ll long long
#define ms(a, b) memset(a, b, sizeof(a))
#define inf 0x3f3f3f3f
#define db double
#define N 15000005
using namespace std;
template <typename T>
inline void read(T &x) {
x = 0; T fl = 1; register char ch = 0;
for (; ch < '0' || ch > '9'; ch = getchar())
if (ch == '-') fl = -1;
for (; ch >= '0' && ch <= '9'; ch = getchar())
x = (x << 1) + (x << 3) + (ch ^ 48);
x *= fl;
}
char s[5];
int g[155][155], ind[155], ans[N];
int cnt, tot, n;
void dfs(int u) {
for (int i = 1; i <= 150; i ++) {
if (g[u][i]) {
g[u][i] --; g[i][u] --;
dfs(i);
}
}
ans[++ cnt] = u;
}
int main() {
read(n);
for (int i = 1; i <= n; i ++) {
scanf("%s", s);
g[s[0]][s[1]] ++, g[s[1]][s[0]] ++;
ind[s[0]] ++, ind[s[1]] ++;
}
int rt = -1;
for (int i = 1; i <= 150; i ++) {
if (ind[i] % 2 == 1) {
tot ++;
if (tot == 1) rt = i;
}
}
if (rt == -1) {
for (int i = 1; i <= 150; i ++) {
if (ind[i]) {
rt = i;
break;
}
}
}
if (tot != 0 && tot != 2) {
printf("No Solution\n");
return 0;
}
dfs(rt);
for (int i = cnt; i >= 1; i --) printf("%c", ans[i]);
return 0;
}