题目描述
给定n个各不相同的无序字母对(区分大小写,无序即字母对中的两个字母可以位置颠倒)。请构造一个有n+1个字母的字符串使得每个字母对都在这个字符串中出现。
输入输出格式
输入格式:
第一行输入一个正整数n。
以下n行每行两个字母,表示这两个字母需要相邻。
输出格式:
输出满足要求的字符串。
如果没有满足要求的字符串,请输出“No Solution”。
如果有多种方案,请输出前面的字母的ASCII编码尽可能小的(字典序最小)的方案
输入输出样例
输入样例#1: 复制
4
aZ
tZ
Xt
aX
输出样例#1: 复制
XaZtX
说明
【数据规模与约定】
不同的无序字母对个数有限,n的规模可以通过计算得到。
算法分析
欧拉路问题,如果不是欧拉路或欧拉回路,那就不能成立。
代码实现
#include<bits/stdc++.h>
using namespace std;
#define N 2001
int a[N][N],du[N],out[N];
int n,cnt=0;
int pos=0;
int pan(char x)//转为数字
{if(x <= 'z' && x >= 'a') return x - 'a' + 27;//小写字母27~52else return x - 'A' + 1; //大写字母1~27
}
int pan2(char x)//转为字母所对应的ASII
{if(x <= 26) return 'A' + x - 1;return 'a' + x - 27;
}
int dfs(int i)
{int j;for(j=1;j<=52;j++){if(a[i][j]==1){a[j][i]=a[i][j]=0;dfs(j);}}out[++pos]=i;//记录
}
int main()
{cin>>n;int i,j;for(i=1;i<=n;i++){char x,y;cin>>x>>y;a[pan(x)][pan(y)]=a[pan(y)][pan(x)]=1;du[pan(x)]++;du[pan(y)]++;}int s=99999999999;for(i=1;i<=52;i++)if(du[i]%2==1) //欧拉路最小起点{s=min(s,i);cnt++;}if(cnt!=0&&cnt!=2) //无结果{cout<<"No Solution"<<endl;return 0;}if(cnt==0)for(i=1;i<=52;i++)//欧拉回路,需要字典排序{if(du[i]){s=i;break;}}dfs(s);for(i=pos;i>=1;i--)printf("%c",pan2(out[i]));return 0;
}