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

 

输出格式：

 

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

 

输入输出样例

输入样例#1：

6alohaarachniddoggopherrattiger

输出样例#1：

aloha.arachnid.dog.gopher.rat.tiger

说明

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

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

 

这一题是典型的欧拉道路题目。  欧拉道路的定义是： 除了起点和终点外， 其他点的“进出” 次数应该相等。 换句话说，除了起点和终点外， 其他点的度数应该是偶数。

对于有向图， 则必须其中一个点的出度恰好比入度大1， 另一个的入度比出度大。

如果奇点数不存在的话， 则可以从任意点出发，最终一定会回到该点（成为欧拉回路）。

题目给的单词量比较大，但是有用的只有首和尾的字母，所以只需要存首尾字母就可以了。 

欧拉道路还有关键的一部是判断这一个图是连通的， 并且只有一个一个连通分支。

这个可以用并查集的方法， 也可一用dfs直接搜索。

 

1.单词作点 可以拼在一起的单词连边。

2.先对单词排序，加边时注意顺序，使找到的第一个欧拉回路即为字典序最小的，后面直接跳出就好了。

3.dfs前初步判断一下是否有解（注意，是初步！！！） 用一些奇怪的方法

4.dfs后，若找到解则输出，否则***。（因为初步判断有解时可能将一些无解的情况放过了）

 

1 #include 
     
        2 using namespace std; 3 const int N=1010,inf=1<<29; 4 int n,len[N],sta[N],cnt[30],top=0; 5 int head[N],to[N*N],next1[N*N],en; 6 bool flag=false,vis[N]; 7 string s[N]; 8 void dfs(int u) 9 {10     if (flag) return ;11     sta[top++]=u;12     vis[u]=true;13     int v;14     for (int i=head[u];i;i=next1[i])15     {16         v=to[i];17         if (!vis[v]) dfs(v);18     }19     //如果链上了所有点，说明成功了 20     if (top==n) flag=true;21     else vis[u]=false,--top;22 }23 //日常数组模拟链表，没毛病 24 void add_edge(int u,int v){25     to[++en]=v,next1[en]=head[u],head[u]=en;26 }27 int main()28 {29     //读入数据 30     cin>>n;31     for (int i=1;i<=n;i++)32         cin>>s[i];33     //排序 34     sort(s+1,s+n+1);35     //记录每个单词长度 36     for (int i=1;i<=n;i++)37         len[i]=s[i].size();38     //头尾比较法寻找配对单词 39     for (int i=1;i<=n;i++)40         for (int j=n;j>=1;j--)41         //i单词的尾和j单词的头相同42         //并且这两个单词不是同一个 43         if (i!=j && s[i][len[i]-1]==s[j][0])44         //给所有配对的单词添加边 45         add_edge(i,j);46     //统计每个字母的入度和出度情况（单词头尾的字母）   47     //因为欧拉图对节点出入度有要求 48     //欧拉道路的定义是： 除了起点和终点外， 其他点的“进出” 次数应该相等。 换句话说，除了起点和终点外， 其他点的度数应该是偶数。49     //对于有向图， 则必须其中一个点的出度恰好比入度大1， 另一个的入度比出度大。50     for (int i=1;i<=n;i++)51         cnt[s[i][0]-'a']++,cnt[s[i][len[i]-1]-'a']--;52     int k=0,h;53     //初步统计是否符合欧拉图，不符合直接输出不可以 54     for (int i=0;i<26;i++){55         if (cnt[i]==1) k++,h=i;56         if (cnt[i]==2) k=2;57         if (k==2) break;58     }59     //说明有两个入口 60     if (k==2) cout<<"***\n";61     //看看这个点是不是起点，因为只有起点才回没有单词的末尾匹配 62     else if (k==1){63         for (int i=1;i<=n;i++)64             if (s[i][0]-'a'==h)65             dfs(i);66     }67     else {68         //k==0的情况，说明成环了69         //取i节点做起始节点看是否成链 70         for (int i=1;i<=n;i++)71             dfs(i);72     }73     if (!flag) {74         cout<<"***\n";75         return 0;76     }77     cout<
     

 

类似题目：

UVa10129