整理的算法模板合集： ACM模板

---

输出n+1个字母，使得n个字母对都在这个字符串中出现，因为是n+1个字母，所以我们可以看出来其实就是一个欧拉路径，因为字母对可以替换顺序，所以我们将每个字母对都连一个无向边，建图，求欧拉回路，这样求出来的就是n+1个字母的字符串，因为是欧拉路径，所以会经过每条边，也就是每一个字母对都会在里面出现。

我们要先判断图是否连通（可以直接用并查集判断，或者看欧拉路径是否包含了n+1个点），如果不连通那么我们求出来的欧拉回路也不会包含所有的字母对。然后再判断是否有欧拉路径，判断的方法就是看奇度点的个数是不是0或者2，注意如果是0的话说明有欧拉回路，那么我们以哪一个字母为起点都可以，所以我们取字典序最小的字母作为起点，这样才能求得字典序最小的答案。

注意我们使用Hierholzers算法求出来的是倒序的，所以我们存的时候就可以直接倒着存n+1个字母，然后直接cout输出即可。

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
typedef long long ll;
const int N = 5007, M = 500007, INF = 0x3f3f3f3f;
const double eps = 1e-6;
const int mod = 80112002;
typedef pair<int, int >PII;int n, m;
int g[N][N];
char ans[N];
int cnt, tot;
string s;
int fa[N];
int d[N];int Find(int x)
{if(fa[x] == x)return x;return fa[x] = Find(fa[x]);
}void dfs(int x)
{for(int i = 65; i <= 125 ; ++ i){if(g[x][i]){g[x][i] -- , g[i][x] -- ;dfs(i);}}ans[tot -- ] = x;
}//找欧拉路径int main()
{scanf("%d", &n);tot = n;for(int i = 1; i <= 500; ++ i)fa[i] = i;for(int i = 1; i <= n; ++ i){cin >> s;int x = s[0], y = s[1];g[x][y] ++ , g[y][x] ++ ;d[y] ++ , d[x] ++ ;int fx = Find(x), fy = Find(y);fa[fx] = fy;}int cnt = 0;for(int i = 65; i <= 125; ++ i){if(Find(i) == i && d[i])cnt ++ ;}if(cnt != 1){//多个祖先，说明有孤立点不是连通图。puts("No Solution");return 0;}cnt = 0;int root = 0;for(int i = 65; i <= 125; ++ i){if(d[i] & 1){if(root == 0)//找字典序最小的起点root = i;cnt ++ ;}}if(cnt && cnt != 2){//奇度点为0或者2才存在欧拉路径puts("No Solution");return 0;}if(root == 0){
//存在欧拉回路，那么任意点都可以作为起点。所以找字典序最小的起点for(int i = 65; i <= 125; ++ i){if(d[i]){root = i;//找到字典序最小的起点break;}}}dfs(root);cout << ans <<endl;return 0;
}