P1127 词链

题目描述

如果单词 X 的末字母与单词 Y 的首字母相同，则 X 与 Y 可以相连成 X.Y。（注意：X、Y 之间是英文的句号 .）。例如，单词 dog 与单词 gopher，则 dog 与 gopher 可以相连成 dog.gopher。

另外还有一些例子：

• dog.gopher
• gopher.rat
• rat.tiger
• aloha.aloha
• arachnid.dog

连接成的词可以与其他单词相连，组成更长的词链，例如：

aloha.arachnid.dog.gopher.rat.tiger

注意到，. 两边的字母一定是相同的。

现在给你一些单词，请你找到字典序最小的词链，使得每个单词在词链中出现且仅出现一次。注意，相同的单词若出现了 k 次就需要输出 k 次。

输入格式

第一行是一个正整数 n$（1 \le n \le 1000）$，代表单词数量。

接下来共有 n 行，每行是一个由 1 到 20 个小写字母组成的单词。

输出格式

只有一行，表示组成字典序最小的词链，若不存在则只输出三个星号 ***。

输入输出样例 #1

输入 #1

6
aloha
arachnid
dog
gopher
rat
tiger

输出 #1

aloha.arachnid.dog.gopher.rat.tiger

说明/提示

• 对于$ 40\% $的数据，有$ n \leq 10$；
• 对于$ 100\% $的数据，有$ n \leq 1000$。

思路

Gemini said

这是一道非常经典的有向图欧拉路径（Eulerian Path）问题。

题目分析：图论建模

我们可以将这道题转化为图论模型：

• 节点（Vertices）：26 个小写英文字母。
  
• 边（Edges）：每个单词对应一条有向边。例如，aloha 表示一条从节点 a 指向节点 a 的有向边，dog 表示一条从 d 指向 g 的有向边。
  

题目要求“每个单词在词链中出现且仅出现一次”，这意味着我们需要在建好的有向图中寻找一条包含所有边的路径，也就是欧拉路径。同时，题目要求结果字典序最小。

核心算法：Hierholzer 算法

判断和寻找有向图欧拉路径的完整步骤如下：

1. 按字典序预处理：首先将所有单词按字典序从小到大排序。这样在建图后，对每个节点，它相邻的边也是按字典序排列的。
2. 验证连通性和度数条件：
   • 有向图存在欧拉路径的充要条件是：
     • 最多只有一个节点的出度比入度大 1（作为起点）。
       
     • 最多只有一个节点的入度比出度大 1（作为终点）。
       
     • 其余所有节点的入度和出度相等。
       
     • 如果所有节点的入度和出度都相等，说明存在欧拉回路，可以从任意包含边的节点出发（为了字典序最小，选字母序最小的有效节点）。
       
     • 所有边必须在一个连通块内。
       
3. DFS 遍历（Hierholzer 算法）：
   • 从确定的起点开始深度优先搜索。
     
   • 遍历当前节点的所有出边，如果边未被访问过，标记为已访问，并递归 DFS 下一个节点。
     
   • 关键点：在递归返回后（即没有出边可走时），将该边加入答案栈。
     
4. 结果逆序：最终栈中的元素出栈顺序（即数组逆序）就是我们要求的路径。如果路径包含的边数不等于 n，说明图不连通，输出 ***。

代码

// Sunshine, sunshine, ladybugs awake!  
// Clap your hooves and do a little shake!  
#include <bits/stdc++.h>  
#define int long long  
#define endl '\n'  
using namespace std;  
  
using PII=pair<int,int> ;  
inline static constexpr int MAXN=26;  
inline static constexpr int mod=998244353;  
  
struct Edge{  
    int to;  
    int id;  
    string word;  
};  
  
void solve() {  
    int n;cin>>n;  
    vector<vector<Edge>> adj(26);  
    vector<string> s(n);  
    for(auto &i:s)cin>>i;  
        sort(s.begin(),s.end());  
        vector<int> indeg(26,0);  
    vector<int> outdeg(26,0);  
        for(int i=0;i<n;i++){  
        int u=s[i][0]-'a';  
        int v=s[i].back()-'a';  
                indeg[v]++;  
        outdeg[u]++;  
                adj[u].push_back({v,i,s[i]});  
    }  
        int st=-1,ed=-1;  
    for(int i=0;i<26;i++){  
        if(outdeg[i]-indeg[i]==1&&st==-1){  
            st=i;  
        }else if(indeg[i]-outdeg[i]==1&&ed==-1)  
            ed=i;  
        else if(indeg[i]!=outdeg[i]){  
            cout<<"No"<<endl;  
            return ;  
        }  
    }  
        if(st==-1){  
        for(int i=0;i<26;i++){  
            if(adj[i].size()){  
                st=i;  
                break;  
            }  
        }  
    }  
    vector<int> used(n,0);  
    vector<int> head(MAXN,0);  
    vector<string> ans;  
        auto dfs=[&](auto& self,int u)->void{  
        while(head[u]!=(int)adj[u].size()){  
            auto edge=adj[u][head[u]];  
            head[u]++;  
            if(!used[edge.id]){  
                used[edge.id]=true;  
                self(self,edge.to);  
                ans.push_back(edge.word);  
            }  
        }        };  
        dfs(dfs,st);  
        if((int)ans.size()!=n){  
        cout<<"***"<<endl;  
        return ;  
    }else{  
        for(int i=(int)ans.size()-1;i>=0;i--){  
            cout<<ans[i]<<(i==0?"":".");  
        }  
    }  
}  
  
signed main() {  
    ios_base::sync_with_stdio(false);  
    cin.tie(NULL);  
    //int t;cin >> t;while (t--)         solve();  
    return 0;  
}