洛谷P1341 无序字母对

题目描述

给定n个各不相同的无序字母对（区分大小写，无序即字母对中的两个字母可以位置颠倒）。请构造一个有n+1个字母的字符串使得每个字母对都在这个字符串中出现。

输入输出格式

输入格式：

第一行输入一个正整数n。

以下n行每行两个字母，表示这两个字母需要相邻。

输出格式：

输出满足要求的字符串。

如果没有满足要求的字符串，请输出“No Solution”。

如果有多种方案，请输出前面的字母的ASCII编码尽可能小的（字典序最小）的方案

输入输出样例

输入样例#1：

4
aZ
tZ
Xt
aX

输出样例#1：

XaZtX

说明

【数据规模与约定】

不同的无序字母对个数有限，n的规模可以通过计算得到。

生气！

本来想刷道水题玩，结果没1A

不但没1A，还WA了好多次！

原因又是数组不够大！

FAQ！

欧拉路

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cmath>
 4 #include<cstring>
 5 #include<algorithm>
 6 using namespace std;
 7 int mp[200][200];
 8 char s[5];
 9 int d[80];
10 int n;
11 int sta[12000];
12 int top=0;
13 void dfs(int s){
14     for(int i=0;i<70;i++){
15         if(mp[s][i]){
16             mp[s][i]=mp[i][s]=0;
17             dfs(i);
18         }
19     }
20     sta[++top]=s;
21     return;
22 }
23 int main(){
24     scanf("%d",&n);
25     int i,j;
26     int tmp=100;
27     for(i=1;i<=n;i++){
28         scanf("%s",s);
29         int u=s[0]-'A',v=s[1]-'A';
30         tmp=min(tmp,u);
31         tmp=min(tmp,v);
32         mp[u][v]=mp[v][u]=1;
33         d[u]++;d[v]++;
34     }
35     int st=-1,cnt=0;
36     for(i=0;i<70;i++){
37         if(d[i]%2==1){
38             if(st==-1)st=i;
39             cnt++;
40         }
41     }
42     if(!cnt)dfs(tmp);
43     else if(cnt==2)dfs(st);
44     else{printf("No Solution
");return 0;}
45     while(top){
46         printf("%c",(sta[top--]+'A'));
47     }
48     return 0;
49 }