传送门

思路

要求能够发现作为首单词的特殊性，首单词要么为字典序第一（词链可以成环），要么首单字母出现次数为尾字母出现次数+ 1（由于词链的合法性，首尾单词成对出现）

DFS参数列表需要有现词链，当前单词位置（为了在有向图中找下一个单词），词链现有单词数（用来定义结束条件）。建图时只要建起每个单词的编号的下一个可能单词的编号之间的有向边。

代码

#include
#include
#include
#include
using namespace std;
string Word[1010];
int N, head[30], tail[30];
bool vis[1010]; vector Gap[1010];
void DFS(string now,int number,int count) 
{
    if (count == N) {
        now[now.size() - 1] = '\0';
        cout << now;
        exit(0);
    }
    for (int i = 0; i < Gap[number].size(); i++)
    {
        if (!vis[Gap[number][i]])
        {
            vis[Gap[number][i]] = true;
            DFS(now + Word[Gap[number][i]] + '.', Gap[number][i], count + 1);
            vis[Gap[number][i]] = false;
        }
    }
}
int main(void)
{
    cin >> N;
    for (int i = 1; i <= N; i++)
    {
        cin >> Word[i];
        head[Word[i][0] - 'a' + 1]++;
        tail[Word[i][Word[i].size() - 1] - 'a' + 1]++;
    }
    sort(Word + 1, Word + N + 1);
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= N; j++)
        {
            if (Word[i][Word[i].size() - 1] == Word[j][0] && j != i)
                Gap[i].push_back(j);
        }
    }
    for (int i = 1; i <= N; i++)
    {
        if (head[Word[i][0]-'a'+1] == tail[Word[i][0]-'a'+1] + 1)
        {
            vis[i] = true;
            DFS(Word[i] + '.', i, 1);
            vis[i] = false;
        }
    }
    vis[1] = true; DFS(Word[1] + '.', 1, 1);
    cout << "***";
    return 0;
}