洛谷P1127 词链
题目链接：P1127 词链 - 洛谷 | 计算机科学教育新生态
题目描述：
如果单词 XX 的末字母与单词 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
注意到，`.` 两边的字母一定是相同的。
现在给你一些单词，请你找到字典序最小的词链，使得每个单词在词链中出现且仅出现一次。注意，相同的单词若出现了 k 次就需要输出 k 次。
输入格式
第一行是一个正整数 n（1≤n≤1000），代表单词数量。
接下来共有 n 行，每行是一个由 1 到 20 个小写字母组成的单词。
输出格式
只有一行，表示组成字典序最小的词链，若不存在则只输出三个星号 `***`。
样例 ：
样例输入
6
aloha
arachnid
dog
gopher
rat
tiger样例输出：
aloha.arachnid.dog.gopher.rat.tiger
解题思路：本蒟蒻看道这道题第一眼想到深搜，为了减少循环次数先对单词进行字典序排序，观察样例不难发现词链的第一个单词作为首字母次数比它作为尾部次数永远多1，举个例子：
a -- a -- a -- b -- b -- c -- c -- d 不难从例子中发现 a 作为词链的第一个字母，它作为单词的首字母的次数为 2，作为单词的尾字 母的次数为 1，多举几个例子也能有这样的结论，因为从第一个单词的尾字母开始到最后一个单 词的首字母结束，每个作为首字母/尾字母的字母的出现次数都是偶数（成对出现）（这个应该很 好理解），然而第一个单词的首字母多出现了一次，它不是成对出现的。当然，也有特殊情况， 就是最后一个单词的尾字母和第一个单词的首字母是一样的（即可以连成一个环）。那么从 1 开 始就行了。
怎么搜索：
从任意一个字符串 s 开始，每次在输入的所有字符串中查找首字母与 s 的尾字母相同的字符串，然后用找到的这个字符串继续搜索，直到搜索到 n 个字符串为止，搜到后直接输出。
「每次在输入的所有字符串中查找首字母与 s 的尾字母相同的字符串」这个过程可以在输入的时候就建图，在首、尾字母相同的两个字符串之间建立一条边，然后搜索的时候直接用建好的这些边找就行了。
代码部分：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1010;
string a[N];//存储单词
vector<int>e[N];//存储图
int ind[N],rnd[N];//记录单词首字母出现次数和尾字母出现的次数
bool vis[N];
int n;
int read()
{
int t = 0, f = 1;
char ch = getchar();
while(ch > '9' || ch < '0') {
if(ch == '-') f = -1;
ch = getchar();
}
while(ch <= '9' && ch >= '0') {
t = t * 10 + ch - '0';
ch = getchar();
}
return t * f;
}
// s: 当前字符串的编号（所有字符串按字典序，编号分别为 1 到 n）
// t: 当前已生成的词链。
// count: 已查找到的字符串个数。
void dfs(int s,string t,int count)
{
if(count == n)
{
t[t.length() - 1] = ' ';// 把最后一个 '.' 去掉
cout<<t;
exit(0);//结束程序
}
for(auto i : e[s])
{
if(!vis[i])
{
vis[i] = true;
dfs(i,t + a[i] + '.',count + 1);
vis[i] = false;
}
}
}
int main()
{
n = read();
for(int i = 1; i <= n; i++)
{
cin >> a[i];
ind[a[i][0]] ++;
rnd[a[i][a[i].length() - 1]]++;
}
sort(a + 1,a + 1 + n);
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
{
if(i != j && a[i][a[i].length()-1] == a[j][0])
e[i].push_back(j);
}
for(int i = 1; i <= n; i++)
{
if(ind[a[i][0]] == rnd[a[i][0]] + 1)
{
vis[i] = true;
dfs(i,a[i] + '.',1);
vis[i] = false;
}
}
vis[1] = true;
dfs(1,a[1] + '.',1);
vis[1] = false;
cout<<"***";
return 0;
}