P1127 Word Chain
我理解的题目意思
找到所有单词的一种字典序最小的排列，使每个单词恰好使用一次，并且相邻两个单词满足前一个单词的尾字符等于后一个单词的首字符。
输入n个单词，相同的单词若出现了 k 次就需要输出 k 次。
$$1≤n≤1000$$解题思路
这个问题可以转化为有向多重图中的欧拉路径问题。
构造有向多重图 G=(V,E)，具体定义如下：
- 顶点集合 V：每个出现在任意单词首字符或尾字符中的字母对应一个顶点。
- 边集合 E：每个给定单词 S_i 对应一条有向边，其起点为单词的首字符，终点为单词的尾字符。即使两个单词的首尾字符相同，也将它们视为不同的边。
- 目标：找到所有单词的一种排列，使每个单词恰好使用一次，并且相邻两个单词满足前一个单词的尾字符等于后一个单词的首字符。 合法的单词排列与图中的欧拉路径一一对应。如果路径的起点与终点相同，则称其为欧拉回路。
进一步定义顶点的度数差：
$\Delta(v)=out\_deg(v)-in\_deg(v)$
欧拉路径存在的基本条件是：
- 所有与边关联的顶点必须属于同一个弱连通分量。
- 以下两种度数情况至少满足一种：
- 所有顶点的入度与出度相等；
- 恰好有一个顶点的度数差为 1，恰好有一个顶点的度数差为 -1，其余顶点的度数差均为 0。 在此基础上，可以得到以下定理。
定理一: 路径的起点选择
定理陈述： 如果一个有向多重图存在一条起点和终点不同的欧拉路径，那么起点必定是唯一一个满足下式的顶点 s：
$out\_deg(s)-in\_deg(s)=1$
证明： 设存在一条欧拉路径 P，其起点为 s，终点为 t，且 $s\ne t$。 由于欧拉路径需要经过图中的每一条边且每条边恰好一次，因此，对于任意既不是起点也不是终点的中间顶点 v，每次进入该顶点后都必须离开该顶点。于是，该顶点的入度与出度相等：
$out\_deg(v)=in\_deg(v)$
对于起点 s，路径从该顶点出发，但最终不会返回该顶点。因此，路径经过起点时，使用的出边比入边多一条，即：
$out\_deg(s)=in\_deg(s)+1$
从而得到：
$\Delta(s)=1$
同理，对于终点 t，路径最终进入该顶点并结束，因此使用的入边比出边多一条，即：
$in\_deg(t)=out\_deg(t)+1$
从而得到：
$\Delta(t)=-1$
综上，欧拉路径的起点是唯一一个满足 $\Delta(v)=1$ 的顶点，终点是唯一一个满足 $\Delta(v)=-1$ 的顶点，其余顶点的度数差均为 0。 因此，如果图中存在满足 $\Delta(v)=1$ 的顶点，那么在欧拉路径存在的前提下，该顶点必定是路径的起点，且起点唯一。
定理二：无解的度数条件
定理陈述： 如果一个有向多重图存在欧拉路径，则至多有一个顶点满足 $\Delta(v)=1$，至多有一个顶点满足 $\Delta(v)=-1$。 此外，如果存在一个满足 $\Delta(v)=1$ 的顶点，那么必须恰好存在一个满足 $\Delta(v)=-1$ 的顶点。 因此，如果有两个或更多顶点的度数差为 1，或者其他顶点的度数配置不满足上述条件，则不存在合法的单词排列。
证明： 对于任意有向多重图，每条边都恰好对一个顶点的出度和另一个顶点的入度各贡献 1。因此，有：
$\sum_{v\in V}out\_deg(v)=\sum_{v\in V}in\_deg(v)=|E|$
两式相减，得到：
$\sum_{v\in V}\left(out\_deg(v)-in\_deg(v)\right)=0$
即：
$\sum_{v\in V}\Delta(v)=0$
假设该图存在欧拉路径。 根据定理一的证明，当路径的起点与终点不同时，起点的度数差为 1，终点的度数差为 -1，其余顶点的度数差均为 0。 如果路径的起点与终点相同，则路径为欧拉回路，此时所有顶点的度数差均为 0。 因此，欧拉路径存在时，图中的度数差只能出现以下两种情况：
- 所有顶点的度数差均为 0。
- 恰好一个顶点的度数差为 1，恰好一个顶点的度数差为 -1，其余顶点的度数差均为 0。 如果存在两个或更多顶点满足 \Delta(v)=1，就不符合欧拉路径的必要度数条件；同样，如果存在其他不符合上述两种情况的度数配置，也不可能形成欧拉路径。 因此，这些情况下不存在合法的单词排列。。
定理三：入度与出度平衡时的欧拉回路
定理陈述： 如果有向多重图中的每个顶点均满足
$out\_deg(v)=in\_deg(v)$
并且所有与边关联的顶点属于同一个弱连通分量，那么该图一定存在欧拉回路。 因此，任何与边关联的顶点都可以作为欧拉回路的起点。 需要注意的是，这并不意味着任意一个给定的单词都可以直接作为某个 DFS 搜索过程的初始单词。
证明： 根据题设，图中的每个顶点均满足入度等于出度，即：
$\forall v\in V,\quad \Delta(v)=0$
同时，所有与边关联的顶点属于同一个弱连通分量。 根据有向图的欧拉回路定理，一个有向图存在欧拉回路的充要条件是：所有非零度顶点属于同一个弱连通分量，并且每个顶点的入度等于出度。 因此，该图存在一条经过每条边恰好一次、最终返回起点的欧拉回路。 由于欧拉回路经过图中每一条边，所以任何与边关联的顶点都可以作为这条回路的起点。
但是，起点顶点的任意性并不等于起始边的任意性。对于具体的 DFS 或回溯算法，即使图中存在欧拉回路，也不能仅凭这一结论就断定任意选择一条初始边都能使搜索成功。算法仍然需要保证所有边均被使用且每条边恰好使用一次。 因此，在满足度数平衡和连通性条件时，图中存在欧拉回路，且其起点可以从任意非零度顶点中选取。
定理四：合法单词排列存在的充要条件
为了完整地刻画问题的解是否存在，可以进一步给出以下定理。
定理陈述： 对于非空单词集合，其对应的有向多重图存在合法的单词排列，当且仅当同时满足以下条件：
- 所有与边关联的顶点属于同一个弱连通分量。
- 所有顶点的度数差满足以下两种情况之一：
- 所有顶点的入度与出度相等；
- 恰好一个顶点的出度比入度大 1，恰好一个顶点的入度比出度大 1，其余顶点的入度与出度相等。 证明： 先证明必要性。 如果存在合法的单词排列，那么该排列对应一条经过每条边恰好一次的欧拉路径。 由于所有边均由同一条路径遍历，因此所有与边关联的顶点必定属于同一个弱连通分量。 根据前述定理，欧拉路径的度数差只能满足两种情况：所有顶点均平衡，或者存在唯一的起点和终点，分别具有 +1 和 -1 的度数差。 因此，上述两个条件是合法单词排列存在的必要条件。
再证明充分性。 如果所有顶点的入度与出度相等，并且满足连通性条件，根据欧拉回路定理，图中存在欧拉回路。因此，可以按照该回路经过每条边一次，从而得到合法的单词排列。 如果恰好一个顶点的度数差为 +1，另一个顶点的度数差为 -1，其余顶点均平衡，并且满足连通性条件，根据有向图的欧拉路径定理，图中存在一条从前者出发、到后者结束的欧拉路径。因此，同样可以得到合法的单词排列。 综上，所述条件既是合法单词排列存在的必要条件，也是充分条件。
代码：
#include <iostream>
#include <cstring>
#include <queue>
#include<cmath>
#include <algorithm>
using namespace std;
int n,start[30],s1[30];
string chosen[1005],s[1005];
bool vis[1005];
void dfs(string s_now,int acc){
if(acc==n){
for(int i=1;i<n;i++){
cout<<chosen[i]<<'.';
}
cout<<chosen[n];
exit(0);
return;
}
char c_now=s_now[s_now.size()-1];
for(int i=start[c_now-'a'];;i++){
if(s[i][0]!=c_now)break;
if(vis[i])continue;
chosen[acc+1]=s[i];
vis[i]=i;
dfs(s[i],acc+1);
vis[i]=0;
}
}
int main(){
cin>>n;
for(int i=1;i<=n;i++)
{cin>>s[i];
s1[s[i][0]-'a']++;
s1[s[i][s[i].length()-1]-'a']--;
}
sort(s+1,s+n+1);
for(int i=1;i<=n;i++){
if(start[s[i][0]-'a']==0)
start[s[i][0]-'a']=i;
}
int k=0,h;
for(int i=0;i<26;i++){
if(s1[i]==1){
k++,h=i;
}
if(s1[i]==2||k==2)break;
}
if(k==1){
for(int i=1;i<=n;i++){
if(s[i][0]-'a'==h){
string s_now=s[i];
chosen[1]=s[i];
vis[i]=1;
dfs(s_now,1);
vis[i]=0;
}
}
}
if(k==0){
for(int i=1;i<=n;i++){
string s_now=s[i];
chosen[1]=s[i];
vis[i]=1;
dfs(s_now,1);
vis[i]=0;
}
}
cout<<"***";
}
- 参考 谷奕勋