题目描述：

如果单词 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。

分析：

每个单词都有头字母和尾字母，不难发现，每条词链都有这样的特点：
除第一个单词外，其余单词的头字母必然有一个尾字母与其对应。
除最后一个单词外，其余单词的尾字母必然有一个头字母与其对应。
显然是一个欧拉路问题。

问题转化为：

一张图中有26（即26个字母，允许有孤立点）个结点，n条有向路（即n个单词），寻找一条欧拉路，使得经过的词链最短。

解决前思考的几个小问题：
问题1：是否有解？记录每个字母的入度和出度，按照欧拉路的判断方法就可以判断，但是要注意环的存在。

问题2：何时词链字典序最小？注意到”.”的ASCII码为46，小于所有字母的ASCII码，所以ab.ba<ba.ab abcd.de < abcdd.de 其实只要把字典序小的尽量排在前面就OK

问题3：如何快速找到某个点的后继边？
最好建立一个索引集。在按字典序将所有字母排序之后，以某个字母为首字母的所有单词都在一个固定区间上

问题4：如何遍历？类似深度优先搜索，每次尽量选择字典序最小的边进行递归。

伪代码：

/*伪代码：*/
int main()
{
    Input();//输入数据
    sort();//排序
    SetPtr();//建立索引集
    if(! IsEulerRoad())    //假如不是欧拉路（但由于环的存在，其实并非充分条件,后面还要判断）
    {
        cout << “***” << endl;
        return 0;
    }
    Travel();    //遍历，并记录答案
    Output();//输出
    return 0;
}

完整AC代码：

#include<iostream>
#include<string>
#include<algorithm>
#include<list>
using namespace std;

string words[1002];//记录所有单词
int mark[1001];//遍历时作标记
int num = 0;//边（即单词）的总数
int Ptr[28];  //索引集，记录words[] 中以26个字母为首字母的第一个单词下标
int Begin;//遍历起点
int ans[1002];//存储遍历路径
int flag = false;//标记是否遍历结束

void SetPtr();    //初始化Ptr
void travel(int s,int depth);
int InDegree[28];//26个字母的入度
int OutDegree[28];//26个字母的出度
bool IsEulerRoad();
int main()
{
    cin >> num;
    for(int i = 0; i < num; ++i)
    {
        cin >> words[i];
        char apple = words[i][0];
        char banana = words[i][words[i].size()-1];

        ++OutDegree[apple - 'a'];
        ++InDegree[banana - 'a'];
    }
    sort(words,words+num);//按字典序排序
    SetPtr();
        if(!IsEulerRoad())
    {
        cout << "***" << endl;
        return 0;
    }


    travel(Begin,1);
    if(!flag)//排除回路的干扰。比如输入数据为：2 a b。 
    {
        cout << "***" <<endl;
        return 0;
    }
    cout << words[ans[0]];
    for(int i = 1; i < num; ++i)
    {
        cout << "." << words[ans[i]];
    }
    cout << endl;
    return 0;
}
void SetPtr()
{
    int j = 0;
    for(int i = 0; i < num; ++i)
    {
        int k = (char)(words[i][0]) - 'a';
            if(k < j)
                continue;
                while(k > j)
                {
                    Ptr[j] = i;
                    ++j;
                }
                Ptr[j] = i;
                ++j;
    }
    for(;j < 27;++j )
        Ptr[j] = num;
    return;
}
void travel(int s,int depth)
{
    ans[depth - 1] = s;
    if(depth == num)
    {
        flag = true;
        return;
    }
    mark[s] = 1;//标记
    int next = (words[s][words[s].size()-1])-'a';
    int start = Ptr[next];
    int end = Ptr[next+1];//索引集派上用场
    for(int itr = start; itr < end; ++itr)//遍历所有边
    {
        if(!mark[itr])
        {
            travel(itr,depth+1);
            mark[itr] = 0;
            if(flag)
                return;//防止继续循环覆盖掉正确答案
        }
    }


}

bool IsEulerRoad()
{
    int Count = 0;
    int In = 0, Out = 0;
    for(int i = 0; i < 26; ++i)
    {
        if(OutDegree[i] != InDegree[i])
        {
            ++Count;
            if(OutDegree[i] > InDegree[i])
            {
                Out = OutDegree[i] - InDegree[i];
                Begin = Ptr[i];//出度大的点应该为起点。假如这句没有执行，说明这张图可能是欧拉图，Begin=0也是正确的;
            }
            else
            {
                    In = InDegree[i] - OutDegree[i];
            }
        }
    }
    if(!Count)
        return true;
    if(Count != 2)
        return false;
    return ((Out == 1)&&(In == 1));
}