一、大力出奇迹，爆搜过样例
开始想的是先把所有字符串按照字典序升序(由小到大)排一下，然后从前向后以每一个单词为起点爆搜一下，
第一个得到的答案就是字典序最小的答案，这个做法是对的，但是会被卡掉，因为复杂度比较高。
关键词：字符串数组+排序+爆搜
结果：80分，2个点(TLE)掉
完整代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
vector<string> str;
vector<int> path;
int n;
bool st[N];
/**
* 功能：爆搜，找出以u为起点，目前的长度是step,目标是找全n个字符串
* @param u 开始的字符串
* @param step 已经找完的字符串数量
* @return
*/
void dfs(int u, int step) {
//递归终止条件，这就是完成了任务，找到了一组
if (step == n) {
for (int i = 0; i < n; i++) {
cout << str[path[i]];
if (i + 1 < n) cout << '.'; //最后一个不输出.，只有前面n-1个输出.
}
exit(0);
}
//找出所有可能的下一步操作哪个字符串
for (int i = 0; i < n; i++) {
//如果当前字符串的尾字符（node[u].back()）与下一个字符串的首字符一样，并且没有使用过的话
if (!st[i] && str[u].back() == str[i][0]) {
path.push_back(i); //进入路径
st[i] = true; //使上
//递归
dfs(i, step + 1);
//回溯
st[i] = false;
path.pop_back();
}
}
}
int main() {
//输入字符串
cin >> n;
string s;
for (int i = 0; i < n; i++) {
cin >> s;
str.push_back(s);
}
//排序
sort(str.begin(), str.end());
//从头开始，一个个尝试，看看哪个开头能跑完全程，找到第一个就退出
for (int i = 0; i < n; i++) {
//清空状态数组，方便下次尝试
memset(st, 0, sizeof st);
//记录路径上的第一个字符串
path.push_back(i);
//标识已使用，防止走回头路
st[i] = true;
//以i开头，进行爆搜
dfs(i, 1);
//回溯
st[i] = false;
path.pop_back();
}
//前面都没有成功，说明没有一个能打的~，那就输出***吧
cout << "***" << endl;
return 0;
}
二、一笔画问题，确定爆搜入口
1、直接爆搜(dfs)会无脑的遍历每一个结点作为起点，造成(TLE)，需要想办法缩小范围。
2、因为题目要求：
（1）首尾相连，可以想到是图
（2）每个字符串只出现一次，欧拉图 ^考查点I^
(3) 给出的字符串，应该就是边。
3、建图：
通过给的所有单词，建图（这个图不用实际地建出来）建图方法：以每一个单词的首尾字母作为结点，
单词作为边建图（此图最多26个结点），所以如果此图是欧拉图，那么必存在一条通路，将所有边访问且仅访问一次，那么就找到了一条词链，否则必定不存在词链。
4、如果想使用欧拉图，必须满足欧拉图的要求（判断欧拉图）,判断是否为欧拉图，若是欧拉图则存在一条词链，否则不存在。
(1)底图（指和有向图长得一摸一样的无向图）是否连通，不连通肯定不是欧拉图，这个可以用并查集判断。 ^考查点II^
(2)记下每一个结点的入度和出度即可，欧拉图需要：
①所有结点都满足入度 = 出度
②只存在一个入度 = 出度 + 1和一个 出度 = 入度 + 1的结点，其他结点满足入度 = 出度
如果上面的两个约束不满足，那么无法构成欧拉图，推翻一批不存在词链的单词。
5、判断后，图必满足(abs)(入度-出度)= 1的结点数(flag) = 0或2
(flag) = 0时，随便找一个结点出发都能一笔画，根据题目要求找以字典序最小的字母为首字母的单词出发(dfs)即可。
(flag) = 2时，找到以那个出度 - 入度 = 1的字母（唯一）为首字母的单词作为起始点，(dfs)一遍就一定可以找到一条词链。
以上两种情况的(dfs)，由于之前已经按照单词字典序排序，所以找到的一定是字典序最小的词链。
综上，其实是利用欧拉图的概念快速找到词链的起始字母，然后搜一遍即可，省去了其他不可能的情况。
如果不是欧拉图，直接输出,如果是欧拉图，那么步骤2还赠送了一份大礼包：找出了欧拉路径的出发点*！
这样，我们就不用一个个字符串挨个做根去深搜了，我们只需要从唯一的一个入口去深搜就行了，爽！！！这不就是减枝吗？如果(n=1000)，我们就提速了(999)倍啊！
但问题也随之而来:一中的深搜，是以字符串为操作关键字的，而在欧拉图判断中，我们拿来的开始点，其实是一个字母映射的ID数字，而不是一个字符串！在欧拉图中，字符串是边的概念，需要在逻辑上进行一下修改。
完整代码:
#include <bits/stdc++.h>
using namespace std;
const int M = 1010; //字符串数量上限,可以理解为边数
const int N = 26; //a-z映射了26个数字,也就是图中结点的数字上限
vector<string> str; //输入的字符串数组
vector<int> path; //结点的搜索路径
int n; //字符串数量
bool st[M]; //是否使用
int fa[N]; //并查集数组
int in[N]; //入度
int out[N]; //出度
unordered_map<int, int> _map;//用来记录某个结点号是否出现过
//并查集，用来判断底图的连通性
int find(int x) {
if (x != fa[x]) fa[x] = find(fa[x]);
return fa[x];
}
//加入家族集合中
void join(int a, int b) {
int f1 = find(a), f2 = find(b);
if (f1 != f2)fa[f1] = f2;
}
/**
* 功能:深度优先搜索
* @param u 从哪个结点ID出发
* @param step 已经走了多少条边
*/
void dfs(int u, int step) {
//如果成功走了n条边，则是成功的标识
if (step == n) {
//输出路径
for (int i = 0; i < path.size(); i++) {
cout << str[path[i]];
if (i < path.size() - 1) cout << '.'; //最后一个不输出.，只有前面n-1个输出.
}
exit(0);
}
//遍历所有可能性，走多叉树，找出欧拉路径,（1）找到就直接退出，（2）从start开始肯定有，这两条保证了效率的提升
for (int i = 0; i < n; i++) {
//找到能和u结点匹配的下一个未使用过的字符串
if (!st[i] && str[i][0] - 'a' == u) {
path.push_back(i); //放入到路径中
st[i] = true; //标识为已使用
//开始尝试下一个字符串
dfs(str[i].back() - 'a', step + 1);
//回溯
st[i] = false; //未使用
path.pop_back(); //路径弹出
}
}
}
int main() {
//输入字符串
cin >> n;
string s;
for (int i = 0; i < n; i++) cin >> s, str.push_back(s);
// 排序确保搜索字典序最小
sort(str.begin(), str.end());
//并查集初始化,每个人都是自己的祖先
for (int i = 0; i < N; i++) fa[i] = i;
//检查一下是不是底图连通,采用并查集,通俗点说：就是看看是不是能全部连通在一起，如果不能，最后是多个家族，则不是欧拉图
for (int i = 0; i < n; i++) {
//每行是一个由 1 到 20 个"小写"字母组成的单词
int a = str[i][0] - 'a'; //首字母映射号,相当于结点编号
int b = str[i].back() - 'a'; //尾字母映射号,相当于结点编号
//转为数字，建立并查集之间的关系，这个字符映射数字用的很妙。
// join合并并查集
join(a, b);
//标识a和b都使用过
_map[a]++, _map[b]++;
//记录b的入度++
in[b]++;
//记录a的出度++
out[a]++;
//之所以记录出度和入度，是为了下一步的欧拉图二次检测
}
// 判断欧拉图的第一个要求：底图连通性
int cnt = 0; //家族的数量
for (int i = 0; i < N; i++) if (fa[i] == i && _map[i]) cnt++;//自己是自己的祖先，并且出现过
//并查集的家族个数大于1，表示不可能是欧拉图
if (cnt > 1) {
cout << "***";
return 0;
}
int flag = 0; //出度与入度差是1的个数
int start = str[0][0] - 'a';//默认是第一个字符串的第一个字符对应的结点
// 判断欧拉图的第二个要求:出度与入度的数字关系
for (int i = 0; i < N; i++) {
//计算每个结点的出度与入度的差
int k = out[i] - in[i];
//出度与入度差大于1，则肯定不是欧拉图
if (abs(k) > 1) {
cout << "***";
return 0;
}
//如果差是1，那么需要检查是不是2个,2个才是一个入口点，一个出口点
if (abs(k) == 1) {
//记录个数
flag++;
//如果出度比入度大1，记录下起点是哪个结点
if (k == 1) start = i;
}
}
//如果不是0也不是2，那么不是欧拉图
if (flag != 0 && flag != 2) {
cout << "***";
return 0;
}
//这时，肯定是有一条欧拉路径的了,找出这条欧拉路径
dfs(start, 0);
return 0;
}