洛谷 P1341 无序字母对 wd

题目描述

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

输入输出格式

输入格式：

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

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

输出格式：

输出满足要求的字符串。

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

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

输入输出样例

输入样例#1：

4
aZ
tZ
Xt
aX

输出样例#1：

XaZtX

说明

【数据规模与约定】

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

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<vector>
 5 #include<stack>
 6 #include<algorithm>
 7 #include<cstdlib>
 8 #include<queue>
 9 #define maxn 3000
10 #define PB(a)   push_back(a)
11 
12 using namespace std;
13 
14 deque<char>ans;
15 vector<int >son[102];
16 
17 int n,in[maxn],checked[maxn],vis[maxn][maxn];
18 
19 struct cur_word 
20 {
21     int a,b,nu;
22     bool operator<(const cur_word r)const 
23     {
24         return a==r.a?b<=r.b:a<=r.a;
25     }
26 } word[2*maxn];
27 
28 void dfs(int u,int deep) 
29 {
30     ans.push_back(u+'A');
31     if(deep==n+1) 
32     {
33         int gg=0;
34         while(!ans.empty()) 
35         {
36             char x=ans.front();
37             printf("%c",x);
38             ans.pop_front();
39         }
40         exit(0);
41     }
42     for(int i=0; i<son[u].size(); i++) 
43     {
44         int y=son[u][i];
45         if(!vis[u][y]&&!vis[y][u]) 
46         {
47             vis[u][y]=1;
48             dfs(y,deep+1);
49             vis[u][y]=0;
50         }
51     }
52     ans.pop_back();
53 }
54 
55 int main() 
56 {
57     scanf("%d",&n);
58     for(int i=1; i<=n; i++) 
59     {
60         char s[3];
61         scanf("%s",s);
62         int a=s[0]-'A',b=s[1]-'A';
63         in[b]++,in[a]++;
64         word[i].a=a,word[i].b=b;
65         word[i+n].a=b,word[i+n].b=a;
66     }
67     sort(word+1,word+2*n+1);
68     int ccnt=0,start2=-1,start0=-1;
69     for(int i=1; i<=2*n; i++) 
70     {
71         int x=word[i].a ,y=word[i].b;
72         son[x].PB(y);
73         son[y].PB(x);
74         if((in[x])%2&&!checked[x]) 
75         {
76             checked[x]=1,ccnt++;
77             if(start0==-1)start0=x;
78         }
79         if(in[x]==2&&start2==-1)start2=x;
80     }
81     if(ccnt!=0&&ccnt!=2) 
82     {
83         printf("No Solution");
84         exit(0);
85     }
86     if(ccnt==2)dfs(start0,1);
87     if(ccnt ==0)dfs(start2,1);
88     return 0;
89 }