-
欧拉路径：欧拉路是指从图中任意一个点开始到图中任意一个点结束的路径，并且图中每条边通过的且只通过一次。
-
欧拉回路:欧拉回路是指起点和终点相同的欧拉路。
注意：如果欧拉回路，那么一定存在欧拉路径
注意：是每条边被访问一次，节点可能会被访问两次。 -
无向图，所有边都是连通的
- 存在欧拉路径的充分必要条件：度数为奇数的点只能是0个或者2个
- 存在欧拉回路的充分必要条件：度数为奇数的只能是0个
-
对于有向图，所有边都是连通的
- 存在欧拉路径的充分必要条件：
- 要么所有点的出度均等于入度。
- 要么除了两个点之外，其余所有点的出度等于入度，剩余的两个点：一个满足出度比入度多1（起点），另一个满足入度比出度多1（终点）。
- 存在欧拉回路的充分必要条件：所有点的出度均等于入度
- 存在欧拉路径的充分必要条件：
例题：p1127 词链
题目描述
如果单词 .）。例如，单词 dog 与单词 gopher，则 dog 与 gopher 可以相连成 dog.gopher。
另外还有一些例子：
dog.gophergopher.ratrat.tigeraloha.alohaarachnid.dog
连接成的词可以与其他单词相连，组成更长的词链，例如：
aloha.arachnid.dog.gopher.rat.tiger
注意到，. 两边的字母一定是相同的。
现在给你一些单词，请你找到字典序最小的词链，使得每个单词在词链中出现且仅出现一次。注意，相同的单词若出现了
输入格式
第一行是一个正整数
接下来共有
输出格式
只有一行，表示组成字典序最小的词链，若不存在则只输出三个星号 ***。
样例 #1
样例输入 #1
6
aloha
arachnid
dog
gopher
rat
tiger
样例输出 #1
aloha.arachnid.dog.gopher.rat.tiger
提示
- 对于
- 对于
题解
看到这题，一般的第一个想法就是暴力搜索。
根据数据范围，搜索应该能拿到 40 分左右的成绩。
下面我们考虑正解。
我们发现，一个单词在词链中与哪些单词拼接，只与这个单词开头和末尾的两个字符有关！
别看这个性质很普通，这恰好是我们数学建模的入手点！
如何数学建模？考虑把单词开头字母向单词结尾字母连边，我们可以得到一个有向图。这时候再看题目，这题就变成了求欧拉路径的问题了。
想到这里，你已经成功了一半了。下面开始考虑判断无解和寻找路径起点的问题。
关于有向图的欧拉路径起点，可以用如下方法寻找：
把一个点的度记为这个点的出度减去这个点的入度。一个有向图存在欧拉路径，则这个路径的起点的度必为 11,终点的度必为 −1−1，其余点的度为 00。如果所有点的度都是 00，则变成欧拉回路，可以从任意点开始搜索。
另外，还要判断无解。无解的情况就是图不连通。有一个判无解的简单方法：搜索完成后，判断是否所有的边都被搜过，如果没有，无解。
另外，题目要求要字典序最小的答案。对此，可以把输入的单词排序后连边。需要注意的是，如果是用边链表存边的，需要倒序连边，才能保证字典序最小。然后如果遇到欧拉回路，则找存在的字母中字典序最小的开始搜索即可。
那么这题就做完了，下面是代码：
#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
#define ll long long
#define rgt register int
using namespace std;
const int mxn = 1010;
string str[mxn],outans[mxn];
int tot,lst[30],nxt[mxn],to[mxn],bh[mxn],d[mxn],lans;
// tot是加到第几条边，lst下标为字母，内容为从该字母出发的边的id（1~id~n）
// nxt下标是第i条边，若该边从字母a出发，则nxt[i]为从字母a出发的下一条边的id（1~id~n）
bool use[mxn];
inline void add(int x,int y,int b){
tot++;
to[tot]=y;
bh[tot]=b; //存这条边对应的字符串编号
d[x]++;
d[y]--; //计算点度
nxt[tot]=lst[x];
lst[x]=tot;
} //加边函数
void dfs(int g){ //搜索函数
for(rgt i=lst[g];i;i=nxt[i]){
if(!use[bh[i]]){ //找到一条未使用的边
use[bh[i]]=true; //标记
dfs(to[i]);
lans++; //倒序存答案
outans[lans]=str[bh[i]];
}
}
}
int main(){
ios::sync_with_stdio(false);
int n,st;
cin>>n;
for(rgt i=1;i<=n;i++)
cin>>str[i]; //读入数据
sort(str+1,str+1+n); //排序
st=str[1][0]-'a'+1; //先把存在的字典序最小的字母作为起点，如果是欧拉回路，则从这个起点切入
for(rgt hd,tl,i=n;i>=1;i--){
hd=str[i][0]-'a'+1; //首字母
tl=str[i][str[i].size()-1]-'a'+1; //尾字母
add(hd,tl,i); //连边
}
for(rgt i=1;i<=26;i++)
if(d[i]==1){ //是欧拉路径，更新起点
st=i;
break;
}
dfs(st);
for(rgt i=1;i<=n;i++)
if(!use[i]){
cout<<"***";
return 0;
} //如果没有使用所有边，无解
for(rgt i=lans;i>1;i--)
cout<<outans[i]<<".";
cout<<outans[1]; //输出答案
return 0;
}
