题目描述
给定n个各不相同的无序字母对（区分大小写，无序即字母对中的两个字母可以位置颠倒）。请构造一个有n+1个字母的字符串使得每个字母对都在这个字符串中出现。
输入输出格式
输入格式：
第一行输入一个正整数n。
以下n行每行两个字母，表示这两个字母需要相邻。
输出格式：
输出满足要求的字符串。
如果没有满足要求的字符串，请输出“No Solution”。
如果有多种方案，请输出前面的字母的ASCII编码尽可能小的（字典序最小）的方案
输入输出样例
输入样例#1： 复制
4
aZ
tZ
Xt
aX
输出样例#1： 复制
XaZtX
说明
【数据规模与约定】
不同的无序字母对个数有限，n的规模可以通过计算得到。
可将两个字母看成两个点，分别用ASCII码值来表示，通过边连接，那么所有的无序字母构成一个无向图。
若存在满足题意的解，那么此图构成欧拉回路。
我们可以想想无向图欧拉回路的定义：所有的点度数都为偶数，或者只有两个点的度数为奇数。
123456789
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
| #include
using namespace std;const int maxn=1005;
int n;
char s[5];
struct edge{int x;int idx;
};
vector g[maxn]; // 运用边集数组建立存储结构
int du[60],vis[maxn],vis1[60];//用vis表示顶点是否访问// 用 vis1 表示 顶点即字母出现过
vector eg; // 用来存储路径
bool cmp(edge aa,edge bb)
{return aa.x2 || cnt ==1)ok=0; // 判断if(ok==0) printf("No Solution\n");else{for(int i=1;i<60;i++) // 因从字母最小的开始遍历，保证第一个字母最小，即字典序最小if(vis1[i]==1){ // 出现过s=i;break;}for(int i=1;i<60;i++)if(du[i]%2==1){ // 从度数为奇数的顶点开始s=i;break;}memset(vis,0,sizeof(vis));dfs(s);// 注意逆序输出 for(int i=eg.size()-1;i>=0;i--) printf("%c",eg[i]-1+'A'); }return 0;
}
|
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！
