P1127

题目描述

如果单词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个小写字母组成的单词

输出格式：

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

输入输出样例

6
aloha
arachnid
dog
gopher
rat
tiger

aloha.arachnid.dog.gopher.rat.tiger

说明

对于40%的数据，有n≤10；

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

字符串排序+搜索

//Serene
#include
#include
#include
#include
#include
#include
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<

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！