洛谷题单指南-图的基本应用-P1127 词链

原题链接：https://www.luogu.com.cn/problem/P1127

题意解读：按字典序排列单词，使得相邻单词的首位字母一样。

解题思路：

由于单词之间可以相邻的条件是前一个单词的末尾字母和后一个单词的开头字母一样，因此可以遍历每一个单词，再找到每一个可以接在其后面的单词，

建立一个邻接表，然后从每一个单词开始，进行DFS，如果能找到n个单词，说明词链构建成功，输出结果即可；由于需要按字典序排列，在建立邻接表前，先把单词排序即可。

80分代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 1005;

string words[N];
vector<int> g[N];
int n;
bool flag[N];

bool dfs(int u, int cnt, string res)
{
    if(cnt == n) //如果已经加了n个单词，输出结果
    {
        cout << res;
        return true;
    }
    for(auto v : g[u]) //找能连在单词u后面的其他单词v，依次枚举、回溯
    {
        if(!flag[v])
        {
            flag[v] = true;
            bool ret = dfs(v, cnt + 1, res + "." + words[v]);
            if(ret) return true; //如果成功，提前结束递归，否则继续回溯
            flag[v] = false;
        }
    }
    return false;
}

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> words[i];
    sort(words + 1, words + n + 1); //按字典序排序
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            if(i != j && words[i][words[i].length() - 1] == words[j][0])
            {
                g[i].push_back(j); //单词i和单词j建立关联
            }
        }
    }
    bool success = false;
    for(int i = 1; i <= n; i++) 
    {
        memset(flag, 0, sizeof(flag));
        flag[i] = true;
        success = dfs(i, 1, words[i]); //从每一个单词开始进行DFS，看是否能找到一条n个单词的词链
        if(success) break;
    }
    if(!success) cout << "***";

    return 0;
}

以上方法的主要问题在于，需要从每一个单词开始进行DFS，会导致部分超时。

分析题意，对于一个词链，除了第一个单词的开头字母以及最后一个单词的结尾字母，其余单词的在开头、结尾字母应该是偶数个；

如果算上第一个单词的开头字母，如果和最后一个单词结尾字母不相等，这个字母出现在单词开头的个数一定比出现在单词结尾的次数多1，

如果找到1个这样的单词，就取该单词作为起点即可找到词链；

如果第一个单词的开头字母和最后一个单词的结尾字母相等，那么将可以形成一个环，从任意一个单词开始都可以构成词链，取字母序最小的即可；

100分代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 1005;

string words[N];
vector<int> g[N];
int n;
bool flag[N];
char front[30], tail[30]; //字母在单词头尾出现的次数

bool dfs(int u, int cnt, string res)
{
    if(cnt == n) //如果已经加了n个单词，输出结果
    {
        cout << res;
        return true;
    }
    for(auto v : g[u]) //找能连在单词u后面的其他单词v，依次枚举、回溯
    {
        if(!flag[v])
        {
            flag[v] = true;
            bool ret = dfs(v, cnt + 1, res + "." + words[v]);
            if(ret) return true; //如果成功，提前结束递归，否则继续回溯
            flag[v] = false;
        }
    }
    return false;
}

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> words[i];
        front[words[i][0] - 'a']++; //头字母出现次数+1
        tail[words[i][words[i].length() - 1] - 'a']++; //尾最出现次数+1
    } 
    sort(words + 1, words + n + 1); //按字典序排序
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            if(i != j && words[i][words[i].length() - 1] == words[j][0])
            {
                g[i].push_back(j); //单词i和单词j建立关联
            }
        }
    }

    bool success = false;
    for(int i = 1; i <= n; i++) 
    {
        if(front[words[i][0] - 'a'] - tail[words[i][0] - 'a'] == 1)
        {
            memset(flag, 0, sizeof(flag));
            flag[i] = true;
            success = dfs(i, 1, words[i]); //从首字母在开头出现次数比结尾出现次数多1的单词开始进行DFS，看是否能找到一条n个单词的词链
            if(success) break;
        } 
    }
    //从第一个单词开始dfs，处理形成环的情况
    if(!success)
    {
        memset(flag, 0, sizeof(flag));
        flag[1] = true;
        success = dfs(1, 1, words[1]);
    }
    
    if(!success) cout << "***";

    return 0;
}