给定n个各不相同的无序字母对(区分大小写,无序即字母对中的两个字母可以位置颠倒)。请构造一个有n+1个字母的字符串使得每个字母对都在这个字符串中出现。
输入格式:
第一行输入一个正整数n。
以下n行每行两个字母,表示这两个字母需要相邻。
输出格式:
输出满足要求的字符串。
如果没有满足要求的字符串,请输出“No Solution”。
如果有多种方案,请输出前面的字母的ASCII编码尽可能小的(字典序最小)的方案
输入样例#1:
4
aZ
tZ
Xt
aX
输出样例#1:
XaZtX
【数据规模与约定】
不同的无序字母对个数有限,n的规模可以通过计算得到。
这题是欧拉回路的裸题
但是有两个地方需要注意
1.在函数中输出不能使用传值变量为循环变量
2.ios::sync容易引起RE!、
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<cmath>
5 #include<cstdlib>
6 using namespace std;
7 const int MAXN=4001;
8 void read(int & n)
9 {
10 char c='+';int x=0;int flag=0;
11 while(c<'0'||c>'9')
12 { c=getchar(); if(c=='-') flag=1; }
13 while(c>='0'&&c<='9')
14 {x=x*10+(c-48);c=getchar();}
15 flag==1?n=-x:n=x;
16 }
17 int n;
18 int map[MAXN][MAXN];
19 int indegree[MAXN];
20 int ans[MAXN];
21 int flag=0;
22 void dfs(int num,int now)
23 {
24 ans[now]=num;
25 if(now==n+1)
26 {
27 for(int i=1;i<=n+1;i++)
28 printf("%c",(char)ans[i]);
29 exit(0);
30 }
31 for(int i=65;i<=127;i++)
32 {
33 if(map[num][i])
34 {
35 map[num][i]=0;
36 map[i][num]=0;
37 dfs(i,now+1);
38 map[num][i]=1;
39 map[i][num]=1;
40 }
41 }
42 ans[now]=0;
43 }
44 int main()
45 {
46 cin>>n;
47 ios::sync_with_stdio(false);
48 for(int i=1;i<=n;i++)
49 {
50 char a,b;
51 cin>>a>>b;
52 if(!map[a][b])
53 {
54 map[a][b]=1;
55 map[b][a]=1;
56 indegree[a]++;
57 indegree[b]++;
58 }
59 }
60 int tot=0;
61 int bgji=0x7fff,bgou=0x7ffff;
62 for(int i=65;i<=127;i++)
63 {
64 if(indegree[i]%2==1)
65 {
66 tot++;
67 bgji=min(bgji,i);
68 }
69 else if(indegree[i])
70 bgou=min(i,bgou);
71 }
72 if(tot!=0&&tot!=2)
73 {
74 printf("No Solution");
75 exit(0);
76 }
77 tot==0?
78 dfs(bgou,1):
79 dfs(bgji,1);
80 return 0;
81 }