题目描述

如果单词X的末字母与单词Y的首字母相同,则X与Y可以相连成X.Y。(注意:X、Y之间是英文的句号“.”)。例如,单词dog与单词gopher,则dog与gopher可以相连成dog.gopher。

另外还有一些例子:

dog.gopher

gopher.rat

rat.tiger

aloha.aloha

arachnid.dog

连接成的词可以与其他单词相连,组成更长的词链,例如:

aloha.arachnid.dog.gopher.rat.tiger

注意到,“.”两边的字母一定是相同的。

现在给你一些单词,请你找到字典序最小的词链,使得这些单词在词链中出现且仅出现一次。

输入输出格式

输入格式:

第一行是一个正整数n(1 ≤ n ≤ 1000),代表单词数量。

接下来共有n行,每行是一个由1到20个小写字母组成的单词

输出格式:

只有一行,表示组成字典序最小的词链,若不存在则只输出三个星号“***”。

输入输出样例

输入样例#1:

6
aloha
arachnid
dog
gopher
rat
tiger
输出样例#1:

aloha.arachnid.dog.gopher.rat.tiger

说明

对于40%的数据,有n≤10;

对于100%的数据,有n≤1000。

字符串排序+搜索

//Serene
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
using namespace std;
const int maxn=1000+10;
int n,cnt[30],len[maxn],ans[maxn],sum;
bool ok,vis[maxn];
string s[maxn]; int fir[maxn],to[maxn*maxn],nxt[maxn*maxn],e=0;
void add(int x,int y) {
to[++e]=y;nxt[e]=fir[x];fir[x]=e;
} void dfs(int pos) {
if(ok) return;
vis[pos]=1;ans[++sum]=pos;
if(sum==n) {
ok=1;return;
}
int x;
for(int y=fir[pos];y;y=nxt[y]) {
x=to[y];
if(vis[x]) continue;
dfs(x);
}
if(!ok) sum--,vis[pos]=0;
} int main() {
scanf("%d",&n);
for(int i=1;i<=n;++i) cin>>s[i];
sort(s+1,s+n+1);
for(int i=1;i<=n;++i) {
len[i]=s[i].size();
cnt[s[i][0]-'a']++;
cnt[s[i][len[i]-1]-'a']--;
}
int tot=0,pp;
for(int i=0;i<26;++i) {
if(cnt[i]==1) tot++,pp=i;
if(cnt[i]==2) tot=2;
}
if(tot>=2) {
printf("***");
return 0;
}
for(int i=1;i<=n;++i) for(int j=n;j>=1;--j)
if(i!=j&&s[i][len[i]-1]==s[j][0]) add(i,j);
if(tot==1) {
for(int i=1;i<=n;++i) if(s[i][0]-'a'==pp) dfs(i);
}
else for(int i=1;i<=n;++i) dfs(i);
if(!ok) printf("***");
else {
cout<<s[ans[1]];
for(int i=2;i<=n;++i) cout<<"."<<s[ans[i]];
}
return 0;
}

  

最新文章

  1. Java 利用 ByteArrayOutputStream 和 ByteArrayInputStream 避免重复读取配置文件
  2. HDU 4081 Qin Shi Huang&#39;s National Road System [次小生成树]
  3. markdown文档编写
  4. c#中的线程一
  5. iOS开发笔记系列-基础6(预处理程序)
  6. C#.net调用axis2webService
  7. c++基础五个题(一)
  8. R︱foreach+doParallel并行+联用迭代器优化内存+并行机器学习算法
  9. 根据class显示或隐藏多个div
  10. Linux的启动流程(一)
  11. ElasticSearch query_string vs multi_match cross_fields query
  12. xamarin android 汉字转拼音
  13. 《React Native 精解与实战》书籍连载「React Native 网络请求与列表绑定」
  14. 用 tensorflow实现DeepFM
  15. 5、JDBC-元信息
  16. 6-16 单词 uva10129
  17. C#中让WebBrowser运行Javascript脚本
  18. hihocoder217周 树形DP
  19. Explorer内存占用偶尔变高导致卡顿
  20. NIO - Buffer

热门文章

  1. python编程:从入门到实践学习笔记
  2. 【vue】openshopping-vue
  3. Liferay 7:Liferay内部博客地址
  4. spring源码学习之容器的扩展(二)
  5. JAVA面试常见问题之常见集合篇
  6. Docx 生成word文档二
  7. mac ssh 远程容易断线解决方案
  8. Java中的String,StringBuffer和StringBuilder
  9. java如何使用 tesseract 4.0.0-1.4.4
  10. 系统日志和内核消息 $ dmesg$ less /var/log/messages$ less /var/log/secure$ less /var/log/auth