题目描述
小明接到一个神秘的任务：对于给定的 n 个没有顺序的字母对（无序代表这两个字母可以前后顺序颠倒，区分大小写）。请构造一个有 (n+1) 个字母的混乱字符串使得每个字母对都在这个字符串中出现。
输入输出格式
输入格式 第一行输入一个正整数 n。表示无序字母对的个数。 第二行到第 (n+1) 行每行两个字母，表示这两个字母需要相邻。 输出格式 输出满足要求的字符串。如果没有满足条件的情况则输出：No Solution。
输入输出样例1
输入
4aZtZXtaX
输出
XaZtX
输入输出样例2
输入
4axxbbaax
输出
abxax
说明提示
如果有多种方案，请输出字典序最小的方案（即满足前面的字母的 ASCII 编码尽可能小）。
例子一：
这里，我们直接转化成图论的题目，相同颜色的路，只能选一条，选了一条之后，另外一条就不能选，要是的所以字母都连起来，这就是主要思路（详情请看代码注释，写的非常详细）
#include <stdio.h>
const int maxn=10000+10;
int n,m,dis[maxn][maxn],s1=maxn,ans;//dis是用来存两点的连接
int ru[maxn],a[maxn];//ru存度数，a存路径
void out(){//写了个输出函数for(int i=ans-1;i>=0;i--)printf("%c",a[i]);
}
void find(int i){//开始找欧拉路，i表示找的当前这个点for(int j=1;j<=150;j++)//最大的小写z是肯定没超过150的，所以枚举点循环到150就行了if(dis[i][j]>0){//如果两点之间有连通dis[i][j]--;//毁图大法好dis[j][i]--;find(j);//搜索下一个点}a[ans++]=i;//记录路径return ;
}
int main(){scanf("%d",&m);for(int i=1;i<=m;i++){char s[2];scanf("%s",s);//这里我是采用string处理的，char也行不影响dis[s[0]][s[1]]++;//记录路径，数组第一维表示当前的点，与第二维的点有，连接dis[s[1]][s[0]]++;ru[s[0]]++;//记录度数ru[s[1]]++;}int cnt=0,h=0;//开始找点for(int i=1;i<=150;i++)//在找度数为奇数的点if(ru[i]%2!=0){//奇数通过 //偶数不通过 cnt++;if(h==0)h=i;//找到最小的奇点 }if(h==0)//找不到奇点，就是另外找点for(int i=0;i<150;i++)if(ru[i]!=0){h=i;break;}if(cnt!=0&&cnt!=2){printf("No Solution");return 0;}find(h);if(ans<m){//这就是我之前所说的巧妙一点的方法，实际上只要搜完以后判断一下，点数是不是相等就行了，因为m组连边，必有m+1个点，前提是不重复cout<<"No Solution";return 0;}out();//输出return 0;//完结散花
}
