题目描述：

给你一些单词，让你首尾串起来串成一串，并且输出一个字典序最小的方案。

解题报告：

一个单词，比如abcde

那么就连接一条a到e的有向边。

那么构成的图一共最多有26个节点。

每条边都代表一个单词。

那么就转化成了：找一条路，遍历所有的边。

就是欧拉通路问题。

遍历欧拉通路的方法：

确定一个起点（出度-入度 = 1，或者等于0（如果存在欧拉回路的话））

从起点开始深搜（首先要保证图中存在欧拉回路或者通路）

dfs(vid, eid)

其中vid表示当前搜到的点。eid表示当前搜到的边（一个点可能会有很多边）

对于每条边，都是等它搜索完了后，把它代表的内容（这里是单词）压入一个栈中。

最后深搜结束后，依次弹栈就是答案。

算法正确，但是证明此处略。

代码如下：其中judge函数是判断图中是否存在欧拉通路，返回值是起点，不存在返回-1.

eul函数就是上述的求解欧拉通路的深搜函数

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct edge{int to, next, id; bool vst;} e[1024];
int v[26], cnt, t, n, cd[26], rd[26], vst[26], g[26][26], ans[1024], num;
void insert(int from, int to, int id)
{
    e[cnt].to = to, e[cnt].next = v[from];
    e[cnt].vst = 0;e[cnt].id = id;v[from] = cnt++;
}
struct pint{char str[26];}x[1024];
bool cmp(pint a, pint b){return strcmp(a.str, b.str) >= 0;}
void dfs(int id)
{
    vst[id] = true;
    for(int i = 0; i < 26; i++)
        if (!vst[i] && g[id][i]) dfs(i);
}
int judge()
{
    int num = 0, id = -1;;
    for(int i = 0; i < 26; i++)
        if (cd[i] - rd[i] == 1) {id = i; num++;}
        else if (rd[i] - cd[i] == 1) num++;
        else if (rd[i] - cd[i] > 1 || rd[i] - cd[i] < -1) return -1;
    if (num > 2) return -1;
    if (id == -1)
        for(int i = 0; i < 26; i++)
            if (cd[i] > 0){id = i; break;}
    memset(vst, 0, sizeof(vst));
    dfs(id);
    for(int i = 0; i < 26; i++)
        if ((cd[i] != 0 || rd[i] != 0) && !vst[i]) return -1;
    if (num > 0)
    {
        for(int i = 0; i < 26; i++) if (cd[i] > rd[i]) return i;
    }
    else
    {
        for(int i = 0; i < 26; i++) if (cd[i] > 0) return i;
    }
    return id;
}
void eul(int vid, int eid)
{
    for(int i = v[vid]; i != -1; i = e[i].next)
        if (!e[i].vst)
        {
            e[i].vst = 1;
            eul(e[i].to, i);
        }
    if(eid >= 0)
        ans[num++] = e[eid].id;
}
int main()
{
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d", &n);
        for(int i = 0; i < n; i++) scanf("%s", x[i].str);
        sort(x, x + n, cmp); memset(vst, 0, sizeof(vst));
        memset(cd, 0, sizeof(cd)); memset(rd, 0, sizeof(rd));
        memset(g, 0, sizeof(g)); cnt = num = 0; memset(v, -1, sizeof(v));
        for(int i = 0; i < n; i++)
        {
            int tmpa = x[i].str[0] - 'a', tmpb = x[i].str[strlen(x[i].str) - 1] - 'a';
            cd[tmpa]++; rd[tmpb]++; insert(tmpa, tmpb, i);
            g[tmpb][tmpa] = g[tmpa][tmpb] = 1;
        }
        int id = judge();
        if (id == -1) printf("***\n");
        else
        {
            num = 0;
            eul(id, -1);
            bool ff = 1;
            for(int i = num - 1; i >= 0; i--)
            {
                if (ff) ff = false;
                else printf(".");
                printf("%s", x[ans[i]].str);
            }
            putchar('\n');
        }
    }
}