题目链接：
poj2337
题意：
给出一些字符串，问能否将这些字符串 按照 词语接龙，首尾相接 的规则 使得每个字符串出现一次
如果可以 按字典序输出这个字符串序列
解题思路：
1.将每个字符串的首尾单词理解为图中的点，，将字符串理解为边构图
2根据入度出度判断是否能构成欧拉路径
3并查集判断连通性
4将所有字符串按字典序排序可以使用sort排序
5欧拉路径的输出 用到fluery算法的思想：
设G 为一无向欧拉图，求G 中一条欧拉回路的算法为：1) 任取G 中一顶点v0，令P0 = v0；2) 假设沿Pi = v0e1v1e2v2 …eivi 走到顶点vi，按下面方法从E(G) – { e1, e2, …, ei }中选ei+1：a) ei+1 与vi 相关联；b) 除非无别的边可供选择，否则ei+1 不应该是Gi = G – { e1, e2, …, ei }中的桥。3) 当2)不能再进行时算法停止。可以证明的是，当算法停止时，所得到的简单回路Pm = v0e1v1e2v2 …emvm, (vm = v0)为G 中一条欧拉回路。
代码：
#include<iostream>#include<cstdio>#include<cstring>#include<vector>#include<algorithm>#define M 1050using namespace std;int n,top;struct edge{int to,vis,id;};vector<edge>w[M];string str[M];int ans[M];int fa[29];int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}void fleury(int loc){for(int i=0; i<w[loc].size(); i++)if(!w[loc][i].vis){w[loc][i].vis=1;fleury(w[loc][i].to);ans[top++]=w[loc][i].id;}return;}int main(){int indegree[28],outdegree[28];int T;scanf("%d",&T);while(T–){top=0;for(int i=0; i<26; i++){w[i].clear();outdegree[i]=indegree[i]=0;fa[i]=i;}scanf("%d",&n);int a,b;for(int i=0; i<n; i++)cin>>str[i];sort(str,str+n);//根据字典序排序int start;for(int i=0; i<n; i++){a=str[i][0]-'a';b=str[i][str[i].size()-1]-'a';indegree[a]++;outdegree[b]++;fa[find(a)]=find(b);w[a].push_back((edge){b,0,i});if(i==0)//重要 起点必须为初始化为第一条边的出节点（字典序最小，且满足 欧拉回路 的的要求）start=a;}int ss=0,num=0,start_num=0,end_num=0;for(int i=0; i<26; i++){if((indegree[i]||outdegree[i])&&find(i)==i)ss++;if(indegree[i]!=outdegree[i]){if(outdegree[i]-indegree[i]==-1)start=i,start_num++;else if(outdegree[i]-indegree[i]==1)end_num++;num++;}}if((num==0||(num==2&&start_num==1&&end_num==1))&&ss==1){fleury(start);for(int i=top-1;i>=0;i–){if(i==0)cout<<str[ans[i]]<<endl;elsecout<<str[ans[i]]<<".";}}elsecout<<"***"<<endl;}return 0;}
放弃等于又一次可以选择的机会。
