P1341 无序字母对
题目描述
给定n个各不相同的无序字母对（区分大小写，无序即字母对中的两个字母可以位置颠倒）。请构造一个有n+1个字母的字符串使得每个字母对都在这个字符串中出现。
输入输出格式
输入格式：
第一行输入一个正整数n。
以下n行每行两个字母，表示这两个字母需要相邻。
输出格式：
输出满足要求的字符串。
如果没有满足要求的字符串，请输出“No Solution”。
如果有多种方案，请输出前面的字母的ASCII编码尽可能小的（字典序最小）的方案
输入输出样例
输入样例#1：
4
aZ
tZ
Xt
aX
输出样例#1：
XaZtX
说明
【数据规模与约定】
不同的无序字母对个数有限，n的规模可以通过计算得到。
/*
容易想到的欧拉回路
当一个图中每个点的度数都是偶数时
存在欧拉环 而只有2个奇数度数时，存在欧拉路径
因此先验证一下然后dfs。
*/ #include<iostream>
#include<cstdio>
#include<cctype>
#include<algorithm>
using namespace std;
const int maxn=,maxe=;
const char *alpha={"ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"};
int N,ans[maxe],ansi=,inde[maxn],S[maxn];
bool has[maxn],G[maxn][maxn]; inline int code(char c) {return c>='a' ? c-'a'+:c-'A';} void dfs(int u,int deep)
{
if(deep==N)
{
ans[ansi++]=u;
return;
}
for(int i=;i<;i++)
if(G[u][i])
{
G[u][i]=G[i][u]=false;
dfs(i,deep+);
if(ansi)
{
ans[ansi++]=u;
return;
}
G[i][u]=G[u][i]=true;
}
} int main()
{
fill(has,has+maxn,false);
fill(inde,inde+maxn,);
fill(G[],G[]+maxn*maxn,false);
cin>>N;
char c;
int x,y,sing=;
for(int i=;i<N;i++)
{
while(!isalpha(c=getchar()));
x=code(c);
while(!isalpha(c=getchar()));
y=code(c);
inde[x]++;
inde[y]++;
has[x]=has[y]=G[x][y]=G[y][x]=true;
}
for(int i=;i<maxn;i++)
if(inde[i]&) S[sing++]=i;
if(sing!=&&sing!=) {cout<<"No Solution"<<endl;return ;}
if(sing==)
dfs(S[],);
else
for(int i=;i<maxn;i++)
if(has[i])
{
dfs(i,);
break;
}
for(int i=ansi-;i>=;i--)
printf("%c",alpha[ans[i]]);
cout<<endl;
return ;
}