一开始看这题，就鸽了，直到寒假才开始正式的写代码，后来在Oi-wiki上自习了欧拉图，看大佬的博客，终于写出来。一道欧拉板子题，但稍有改动。
- 首先一开始，我想到的是爆搜，但很快否决掉了，我们可以看一下这幅图。
我们可以列出以下字母对
aXtza
aZtXa
XtZaX
XaZtX
tZaXt
tXaZt
ZaXtz
ZtXaZ
其中XaZtX便是答案，我们就可以得到一个思路，先搜索出所有的字母对，再在其中找字典序最小的。
不过我们可以从字典序最小的搜，这样搜索出的第一条字母对就是答案。
- 然后我们引入几个概念。
- 欧拉图：可以从其中一点出发，不重复的走完所有点。
- 欧拉回路：可以从其中一点出发，不重复的走完所有点，并且回到了原点。
由此我们发现欧拉回路是一种特殊的欧拉路，而我们上面的图就是一个欧拉回路。但是题目中有无解情况，所以我们要判断无解，那什么是无解，就是该图不是欧拉图的时候，那么怎么判断是不是欧拉图呢？
- 欧拉图是联通的。
- 对于无向欧拉图有0或2个点的边是奇数（有0个点的边是奇数，代表该图是欧拉回路，有两个点代表这两个点是终点或起点）。
符合以上条件的就是欧拉图，就是有解。
- 总体思路就是首先以字母为节点，在用邻接矩阵存图，判断是否为欧拉图，找到字典序最小的，继续dfs在它连着的节点中字典序最小的，直到dfs整个图，所走过的节点便是答案。
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int n,v[1000][1000],dre[1000],start=1001,cnt;
char a,b;
vector<int>ans;
string error="No Solution";
void dfs(int x){for(int i=0;i<1000;++i){//从字典序小的开始搜索if(v[x][i]){v[x][i]=v[i][x]=0;dfs(i);}}ans.push_back(x);//将答案放进vector
}
int main(){cin>>n;for(int i=1;i<=n;i++){cin>>a>>b;int c,d;c=a-'A';//改成数字，方便操作。d=b-'A';v[c][d]=v[d][c]=1;//增加边。dre[d]++;dre[c]++;//读书加1。}for(int i=0;i<1000;++i){if(dre[i]&1){//该点度数是奇数cnt++;//记录奇数点个数start=min(start,i);//找最小字典序。}}if(cnt!=0&&cnt!=2){//判读无解cout<<error;return 0;}if(cnt==0){//如奇数点是0，则是欧拉回路。for(int i=0;i<1000;++i){if(dre[i]){//找一个字典序最小，有边就可以当起点。start=i;break;}}}dfs(start);//搜索for(int i=ans.size()-1;i>=0;i--){cout<<char(ans[i]+'A');//倒序输出}return 0;
}