洛谷：P1127：词链

题目

P1127：词链

分析

这道题有一定的难度。首先，需要掌握一些数学概念。根据题意，有这么几个基本的东西需要理解、掌握。

什么是“接龙”

按照题意，如果存储在单词?..........*和*........~，那么这两个单词可以接龙：因为第一个单词的尾字母*和第二个单词的首字母*相同。那么，如果所有的单词能够连成一个串，有怎样的特点？

形成一条链（欧拉回路）的判断

如果能形成这样一个链——欧拉回路，那么这个回路一定有这样的特点：

• 起点：出度（从这里出发）比入度（达到这里）多1，且只能有一个。
• 终点：出度比入度少1，且只能有一个。

• 中间点：出度等于入度

  或者：每个点都是中间点。

确定是否在这些单词中存在一个欧拉回路，必须要进行这些检查。

//在所有节点中检查是否存在欧拉回路：
// vertices - 存放节点（一个单词）
// eulerStart/eulerEnd - 欧拉回路的起点和终点
string checkEulerPath(const vector<Vertex>& vertices, int& eulerStart,
                      int& eulerEnd)
{
    // 检查每个节点的入度和出度
    for (int i = 1; i <= 26; i++)
    {
        if (!vertices[i].exists) //以字母`i`开头的节点不存在
        {
            continue;
        }

        if (vertices[i].out == vertices[i].in + 1) //起点要求：出度=入度+1
        {
            // 可能的起点
            if (eulerStart)
            {
                return "存在多个起点，无法形成欧拉路径"; //但不能多于一个
            }
            eulerStart = i;
        }
        else if (vertices[i].in == vertices[i].out + 1) //终点要求：入度=出度+1
        {
            // 可能的终点
            if (eulerEnd) //但不能多于一个
            {
                return "存在多个终点，无法形成欧拉路径";
            }
            eulerEnd = i;
        }
        else if (vertices[i].in == vertices[i].out)
        {
            // 正常节点，入度等于出度
            continue;
        }
        else
        {
            return "存在节点的入度和出度差值大于1，无法形成欧拉路径";
        }
    }

    // 检查起点和终点是否成对出现
    if ((eulerStart && !eulerEnd) || (!eulerStart && eulerEnd)) //必须有一个起点、一个终点，或者所有点都是中间点。
    {
        return "起点和终点必须同时存在或同时不存在";
    }

    // 通过所有检查，欧拉路径存在
    return "";
}

DFS找欧拉回路

这种找到路径的方式用DFS会更好。

基本思路是：

1. 从起点开始，递归地访问所有未访问的边
2. 使用vis数组标记已访问的边，避免重复访问
3. 当找到包含所有单词的路径时输出结果

void dfs(int step, int current, int prevEdge, int n,
         const vector<vector<Edge>>& graph, vector<int>& visited,
         vector<string>& result, vector<string>& words)
{
    if (step == n) //一共n个单词，已经找到了第n个，完成了
    {
        for (int i = 1; i <= n; i++)
        {
            cout << result[i];
            if (i < n)
                cout << ".";
        }
        exit(0);
    }

    for (size_t k = 0; k < graph[current].size(); k++) //遍历当前节点的“边”
    {
        const Edge& edge = graph[current][k]; 
        if (!visited[edge.ord]) //没访问过才继续深入
        {
            visited[edge.ord] = 1;
            result[step + 1] = edge.word;
            dfs(step + 1, edge.to, edge.ord, n, graph, visited, result, words);
        }
    }

    visited[prevEdge] = 0;  // 回溯
}

其他数据结构

节点的结构如下：

struct Vertex
{
    bool exists = false;  // 标记字母是否出现
    int in = 0;           // 入度
    int out = 0;          // 出度
};

边的结构如下：

struct Edge
{
    int to;       // 目标节点，只要记录一个字母（转换为1基索引即可）
    int ord;      // 单词序号
    string word;  // 单词本身
};

由于不同的单词可能有同一个首字母，所以要加一个ord字段来标记自己。

答案

思考

“欧拉回路”这个名词有点高大上，但实际上就是“一笔画”的数学定义。

回忆欧拉处理哥尼斯堡七桥问题的时候得到的结论，我们就可以得到上述题解中的大部分思路。