在知乎阅读以获得最佳体验。

以下是正确代码。

遍历搜索，时间复杂度$\mathcal{O}(n^2)$。

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

struct directedEdge{//有向边。
    char edge[31];//记录该边代表的单词。
    int edgeBgn, edgeEnd;//用数字记录该边的起点和终点，即该单词的首字母和末字母（a~z: 1~26，使用数字是方便计算入度出度时取指标）。
} words[1001];//将单词看作连接首字母和末字母的有向边。

int totNumWords;//总共有多少单词，也即边的总数。
int inDegree[27], outDegree[27];//每个节点的入度和出度，由于英文字母只有26个，因此开到26 + 1。
int routeOrder[1001];//记录路径顺序。
bool isUsed[1001];//记录该单词在连接中是否被用过。

int findGraphBgnIfEulerPath(){
    //判断是否可能构成欧拉通路，若是，找到图的起点（第一个单词的首字母）。
    int numGraphBgn = 0, numGraphEnd = 0;//记录该图有几个可能的起点和终点。
    int indexGraphBgn;//记录起点的指标（是第几个字母）。
    int i;//循环变量。
    for(i = 1; i <= 26; i ++){
        if(abs(inDegree[i] - outDegree[i]) >= 2){
            //若入度和出度差值的绝对值大于等于2则不可能是欧拉通路。
            return 0;
        }
        else if(inDegree[i] - outDegree[i] == -1){
            //若入度和出度差值为-1则该点符合欧拉通路起点要求。
            numGraphBgn ++;
            indexGraphBgn = i;//第i个字母就是起点。
        }
        else if(inDegree[i] - outDegree[i] == 1){
            //若入度和出度差值为1则该点符合欧拉通路终点要求。
            numGraphEnd ++;
        }
    }
    if(numGraphBgn > 1 || numGraphEnd > 1){
        //起点或终点多于一个，肯定不是欧拉通路。
        return 0;
    }
    if(numGraphBgn == 1 && numGraphEnd == 1){
        //一个起点一个终点？欧拉通路，启动！
        return indexGraphBgn;
    }
    if(numGraphBgn == 0 && numGraphEnd == 0){
        //没有起点和终点？欧拉回路，启动！
        for(i = 1; i <= 26; i ++){
            if(outDegree[i]){
                //选择有出度的且字典序最小的节点（字母）作为起点。
                return i;
            }
        }
    }
    //只有一个起点、只有一个终点或（没有起点终点且不存在有出度的节点），则不构成欧拉通路。
    return 0;
}

bool cmp(directedEdge e, directedEdge f){
    //判断字典序，e上的单词是否小于f上的单词（e小于f时strcmp()函数返回负数）。
    return strcmp(e.edge, f.edge) < 0;
}

bool isConnected(int partialBgn, int cnt){
    /*
    判断图是否连通，同时记录连接单词的序，即我们的连通路径是先后通过哪些有向边走过的。
    若不连通，也不可能构成欧拉通路。
    解释变量：该次连通性判断从节点partialBgn开始，已判断过cnt条边（cnt是count的缩写），总共有totNumWords条边（单词数量就是边的数量）。
    */
    int i;//循环变量。
    if(cnt == totNumWords + 1){
        //全部判断完毕，连通。
        return true;
    }
    for(i = 1; i <= totNumWords; i ++){
        /*
        我们对图连通性的判断是基于所有节点已经按照字典序从小到大顺序排列完毕。
        因此，我们遍历每一条边，若该边起点的字典序小于我们本次判断开始的节点partialBgn则跳过。
        当某条边起点（设该边为eWord）与我们本次判断开始的节点相同时，我们便跳过了if和else if，进入第85行。
        进入85行之后若能够连通则本次判断isConnected直接return结束了，不会有进入第82行else if的机会。
        由于我们是按照字典序排列的，若有某边起点字典序大于判断开始的节点且该边未在85行之后被标记用过，则说明没有和partialBgn相同的边起点，不连通。
        */
        if(words[i].edgeBgn < partialBgn || isUsed[i]){
            continue;
        }
        else if(words[i].edgeBgn > partialBgn){
            return false;
        }
        isUsed[i] = true;//先将边eWord标记为使用过。
        routeOrder[cnt] = i;//记录遍历顺序，这是第cnt次判断，假设第cnt次经过的是第i条边eWord时该图能够连通。
        if(isConnected(words[i].edgeEnd, cnt + 1)){
            /*
            令边eWord的终点为下次判断的开始节点，并更新判断次数，以记录遍历边的顺序。
            若从eWord的终点开始剩下的没被用过的节点（isUsed中没标记的）能够连通，则直接返回能够连通。
            */
            return true;
        }
        //程序能走到这里说明上一个if的判断为假，第cnt次遍历eWord边并不能使得图（按最小路径）连通，所以记得把这条边重新置为未用过的状态。
        isUsed[i] = false;
    }
    //跳出循环了都没搜到能和判断开始的节点相同的边起点，肯定不连通。
    return false;
}

int main(){
    int t, len;
    int i;//循环变量。
    int initNode;//在找欧拉通路起点的函数中产生的结果导入该变量里。
    scanf("%d", &t);
    while(t --){
        memset(isUsed, false, sizeof(isUsed));
        memset(inDegree, 0, sizeof(inDegree));
        memset(outDegree, 0, sizeof(outDegree));
        //初始化记录数组。
        scanf("%d", &totNumWords);
        for(i = 1; i <= totNumWords; i++){
            scanf("%s", words[i].edge);
            len = strlen(words[i].edge);
            words[i].edgeBgn = words[i].edge[0] - 'a' + 1;//这里需要我讲的话说明你没到做这道题的时候。
            words[i].edgeEnd = words[i].edge[len - 1] - 'a' + 1;//乖乖回去做前面的题。
            inDegree[words[i].edgeEnd] ++;
            outDegree[words[i].edgeBgn] ++;
        }
        initNode = findGraphBgnIfEulerPath();
        if(!initNode){//若返回0说明不存在欧拉通路，具体解释看函数内注释。
            printf("***\n");
            continue;
        }
        sort(words + 1, words + totNumWords + 1, cmp);//提前为isConnected函数排序，方便连通性判断。
        if(!isConnected(initNode, 1)){
            printf("***\n");
            continue;
        }
        for(i = 1; i < totNumWords; i ++){
            printf("%s.", words[routeOrder[i]].edge);
        }
        printf("%s\n", words[routeOrder[totNumWords]].edge);
    }
    return 0;
}

使用二分法，时间复杂度$\mathcal{O}(n\log n)$。

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

struct directedEdge{//有向边。
    char edge[31];//记录该边代表的单词。
    int edgeBgn, edgeEnd;//用数字记录该边的起点和终点，即该单词的首字母和末字母（a~z: 1~26，使用数字是方便计算入度出度时取指标）。
} words[1001];//将单词看作连接首字母和末字母的有向边。

int totNumWords;//总共有多少单词，也即边的总数。
int inDegree[27], outDegree[27];//每个节点的入度和出度，由于英文字母只有26个，因此开到26 + 1。
int routeOrder[1001];//记录路径顺序。
bool isUsed[1001];//记录该单词在连接中是否被用过。

int findGraphBgnIfEulerPath(){
    //判断是否可能构成欧拉通路，若是，找到图的起点（第一个单词的首字母）。
    int numGraphBgn = 0, numGraphEnd = 0;//记录该图有几个可能的起点和终点。
    int indexGraphBgn;//记录起点的指标（是第几个字母）。
    int i;//循环变量。
    for(i = 1; i <= 26; ++ i){
        if(abs(inDegree[i] - outDegree[i]) >= 2){
            //若入度和出度差值的绝对值大于等于2则不可能是欧拉通路。
            return 0;
        }
        else if(inDegree[i] - outDegree[i] == -1){
            //若入度和出度差值为-1则该点符合欧拉通路起点要求。
            numGraphBgn ++;
            indexGraphBgn = i;//第i个字母就是起点。
        }
        else if(inDegree[i] - outDegree[i] == 1){
            //若入度和出度差值为1则该点符合欧拉通路终点要求。
            numGraphEnd ++;
        }
    }
    if(numGraphBgn > 1 || numGraphEnd > 1){
        //起点或终点多于一个，肯定不是欧拉通路。
        return 0;
    }
    if(numGraphBgn == 1 && numGraphEnd == 1){
        //一个起点一个终点？欧拉通路，启动！
        return indexGraphBgn;
    }
    if(numGraphBgn == 0 && numGraphEnd == 0){
        //没有起点和终点？欧拉回路，启动！
        for(i = 1; i <= 26; ++ i){
            if(outDegree[i]){
                //选择有出度的且字典序最小的节点（字母）作为起点。
                return i;
            }
        }
    }
    //只有一个起点、只有一个终点或（没有起点终点且不存在有出度的节点），则不构成欧拉通路。
    return 0;
}

bool cmp(directedEdge e, directedEdge f){
    //判断字典序，e上的单词是否小于f上的单词（e小于f时strcmp()函数返回负数）。
    return strcmp(e.edge, f.edge) < 0;
}

bool isConnected(int partialBgn, int cnt){
    /*
    判断图是否连通，同时记录连接单词的序，即我们的连通路径是先后通过哪些有向边走过的。
    若不连通，也不可能构成欧拉通路。
    解释变量：该次连通性判断从节点partialBgn开始，已判断过cnt条边（cnt是count的缩写），总共有totNumWords条边（单词数量就是边的数量）。
    */
    if(cnt == totNumWords + 1){
        //全部判断完毕，连通。
        return true;
    }
    int i;//循环变量。
    int l, r, mid;//二分查找。
    l = 1;
    r = totNumWords;
    while(l <= r){
        //优化查找以partialBgn为起点的边的循环，用二分将每一次O(n)的查找降到O(logn)。
        mid = (l + r) / 2;
        if(words[mid].edgeBgn == partialBgn){
            break;
        }
        else if(words[mid].edgeBgn > partialBgn){
            r = mid - 1;
        }
        else{
            l = mid + 1;
        }
    }
    if(l > r){
        //没找到，病名为寄。
        return false;
    }
    while(words[mid].edgeBgn == partialBgn && mid > 0){
        //找到的第mid条边并不一定是字典序最小的，寻找字典序最小的边使得其起点为partialBgn。
        -- mid;
    }
    for(i = mid + 1; words[i].edgeBgn == partialBgn; ++ i){
        /*
        跳出while循环的mid是多减了1的，要加上。
        在所有以partialBgn作为起点的边中搜索通路。
        */
        if(!isUsed[i]){//若该边没被用过。
            isUsed[i] = true;//标记为用过。
            routeOrder[cnt] = i;//记录遍历路径。
            if(isConnected(words[i].edgeEnd, cnt + 1)){
                //如果在这条边的基础上能够连通，返回true结束函数。
                return true;
            }
            //上一步if没结束函数，说明第cnt次扫过这条边不能保证连通，不使用这条边，重置使用状态。
            isUsed[i] = false;
        }
    }
    //没搜到能和判断开始的节点相同的边起点，肯定不连通。
    return false;
}

int main(){
    int n, len;
    int i;//循环变量。
    int initNode;//在找欧拉通路起点的函数中产生的结果导入该变量里。
    scanf("%d", &n);
    while(n --){
        memset(isUsed, false, sizeof(isUsed));
        memset(inDegree, 0, sizeof(inDegree));
        memset(outDegree, 0, sizeof(outDegree));
        //初始化记录数组。
        scanf("%d", &totNumWords);
        for(i = 1; i <= totNumWords; ++ i){
            scanf("%s", words[i].edge);
            len = strlen(words[i].edge);
            words[i].edgeBgn = words[i].edge[0] - 'a' + 1;//这里需要我讲的话说明你没到做这道题的时候。
            words[i].edgeEnd = words[i].edge[len - 1] - 'a' + 1;//乖乖回去做前面的题。
            ++ inDegree[words[i].edgeEnd];
            ++ outDegree[words[i].edgeBgn];
        }
        initNode = findGraphBgnIfEulerPath();
        if(!initNode){//若返回0说明不存在欧拉通路，具体解释看函数内注释。
            printf("***\n");
            continue;
        }
        sort(words + 1, words + totNumWords + 1, cmp);//提前为isConnected函数排序，方便连通性判断。
        if(!isConnected(initNode, 1)){
            printf("***\n");
            continue;
        }
        for(i = 1; i < totNumWords; ++ i){
            printf("%s.", words[routeOrder[i]].edge);
        }
        printf("%s\n", words[routeOrder[totNumWords]].edge);
    }
    return 0;
}

字典序最小欧拉路

首先跑一个出度减入度。

1、如果存在一个为1一个为-1，则为出度减入度为1的点是唯一合法的起点

2、如果入度减出度都为0，则任意点都是合法的起点，为了字典序最小，需要选择字典序最小的字母做起点

3、如果有多个为1或者存在出度减度数大于1的则无解

其次需要连通，可以读入边时做并查集，确定起点后，扫一遍图上的点，看看是否和起点在一个连通块里即可

做完之后就已经确定有解了，考虑首先跑一个字典序最小的合法的路。这有可能导致有些边没有被加入，例如这种情况：

图片不会加，你就考虑abcd一条线过去了，但是比如b还有个环befgb，这种如何解决呢？

只需要从后往前扫描刚跑出来的路上的点，如果还有边没加进去，就贪心地选最劣的边往里加即可。 代码使用了stack来回倒，复杂度$tnlogn$。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll read()
{
    ll x;
    cin>>x;
    return x;
}
int n,ru[200],fa[200],flag,now;
multiset<string>o[200];
stack<string>print,ans;
int get(int x)
{
    return fa[x]==x?x:fa[x]=get(fa[x]);
}
void merge(int x,int y)
{
    if(x!=y)
        fa[x]=y;
}
void work()
{
    n=read();
    for(int i='a';i<='z';i++)
    {
        o[i].clear();
        ru[i]=0;
        fa[i]=i;
    }
    while(ans.size())
        ans.pop();
    for(int i=1;i<=n;i++)
    {
        string s;
        cin>>s;
        o[s[0]].insert(s);
        ru[s[0]]++;
        ru[s.back()]--;
        merge(get(s[0]),get(s.back()));
    }
    now=-1;
    for(int i='a';i<='z';i++)
    {
        if(ru[i]==1)
        {
            if(now==-1)
                now=i;
            else
            {
                printf("***\n");
                return ;
            }
        }
        if(ru[i]>1||ru[i]<-1)
        {
            printf("***\n");
            return ;
        }
    }
    if(now==-1)
    {
        for(int i='a';i<='z';i++)
            if(o[i].size())
            {
                now=i;
                break;
            }
    }
    for(int i='a';i<='z';i++)
        if(o[i].size()&&get(i)!=get(now))
        {
            cout<<"***\n";
            return;
        }
    while(o[now].size())
    {
        int t=now;
        string s=*o[now].begin();
        ans.push(s);
        now=s.back();
        o[t].erase(o[t].find(s));
    }
    flag=0;
    while(ans.size())
    {
        while(o[ans.top().back()].size())
        {
            now=ans.top().back();
            while(o[now].size())
            {
                int t=now;
                ans.push(*o[now].begin());
                now=(*o[now].begin()).back();
                o[t].erase(o[t].begin());
            }
        }
        print.push(ans.top());
        ans.pop();
    }
    cout<<print.top();
    print.pop();
    while(print.size())
    {
        cout<<'.'<<print.top();
        print.pop();
    }
    cout<<'\n';
}
int main()
{
    // freopen("1.in","r",stdin);
    for(int t=read();t;t--)
        work();
}
using namespace std;
typedef long long ll;
ll read()
{
    ll x;
    cin>>x;
    return x;
}
int n,ru[200],fa[200],flag,now;
multiset<string>o[200];
stack<string>print,ans;
int get(int x)
{
    return fa[x]==x?x:fa[x]=get(fa[x]);
}
void merge(int x,int y)
{
    if(x!=y)
        fa[x]=y;
}
void work()
{
    n=read();
    for(int i='a';i<='z';i++)
    {
        o[i].clear();
        ru[i]=0;
        fa[i]=i;
    }
    while(ans.size())
        ans.pop();
    for(int i=1;i<=n;i++)
    {
        string s;
        cin>>s;
        o[s[0]].insert(s);
        ru[s[0]]++;
        ru[s.back()]--;
        merge(get(s[0]),get(s.back()));
    }
    now=-1;
    for(int i='a';i<='z';i++)
    {
        if(ru[i]==1)
        {
            if(now==-1)
                now=i;
            else
            {
                printf("***\n");
                return ;
            }
        }
        if(ru[i]>1||ru[i]<-1)
        {
            printf("***\n");
            return ;
        }
    }
    if(now==-1)
    {
        for(int i='a';i<='z';i++)
            if(o[i].size())
            {
                now=i;
                break;
            }
    }
    for(int i='a';i<='z';i++)
        if(o[i].size()&&get(i)!=get(now))
        {
            cout<<"***\n";
            return;
        }
    while(o[now].size())
    {
        int t=now;
        string s=*o[now].begin();
        ans.push(s);
        now=s.back();
        o[t].erase(o[t].find(s));
    }
    flag=0;
    while(ans.size())
    {
        while(o[ans.top().back()].size())
        {
            now=ans.top().back();
            while(o[now].size())
            {
                int t=now;
                ans.push(*o[now].begin());
                now=(*o[now].begin()).back();
                o[t].erase(o[t].begin());
            }
        }
        print.push(ans.top());
        ans.pop();
    }
    cout<<print.top();
    print.pop();
    while(print.size())
    {
        cout<<'.'<<print.top();
        print.pop();
    }
    cout<<'\n';
}
int main()
{
    // freopen("1.in","r",stdin);
    for(int t=read();t;t--)
        work();
}

可以学一下欧拉回路（需要用到深度优先搜索）