http://poj.org/problem?id=2337

题意:

判断给出的单词能否首尾相连,输出字典序最小的欧拉路径。

思路:

因为要按字典序大小输出路径,所以先将字符串排序,这样加边的时候就会优先加字典序小的边,dfs的时候也就会先走字典序小的边。

判断一下图的连通性以及是否存在欧拉道路。

然后进行深搜寻找欧拉路径,因为欧拉路径时要逆序输出的,所以这里需要先保存起来,最后再次逆序输出即可得到正确的路径。

 #include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<sstream>
#include<vector>
#include<stack>
#include<queue>
#include<cmath>
#include<map>
#include<set>
using namespace std;
typedef long long ll;
typedef long long ull;
typedef pair<int,int> pll;
const int INF = 0x3f3f3f3f;
const int maxn = + ; struct Edge
{
int ID;
int v;
int vis;
Edge(){}
Edge(int id,int x,int y):ID(id),v(x),vis(y){}
}; int n;
int p[];
int in[], out[];
string str[maxn]; vector<Edge> G[maxn]; stack<int> sta; int Find(int x)
{
return p[x]==x?x:p[x]=Find(p[x]);
} void Fleury(int u)
{
for(int i=;i<G[u].size();i++)
{
if(!G[u][i].vis)
{
G[u][i].vis=;
Fleury(G[u][i].v);
sta.push(G[u][i].ID); //这儿是逆序存储
}
}
} int main()
{
//freopen("in.txt","r",stdin);
int T;
scanf("%d",&T);
while(T--)
{
memset(in,,sizeof(in));
memset(out,,sizeof(out)); scanf("%d",&n);
for(int i=;i<;i++) {G[i].clear();p[i]=i;} for(int i=;i<n;i++) cin>>str[i];
sort(str,str+n); //排序,按照字典序顺序加边,这样等下dfs的时候就会先选择字典序小的边 int start;
for(int i=;i<n;i++)
{
int a=str[i][]-'a';
int b=str[i][str[i].size()-]-'a';
out[a]++;
in[b]++;
int x=Find(a);
int y=Find(b);
if(x!=y) p[x]=y;
G[a].push_back(Edge(i,b,));
if(i==) start=a;
} int cnt=;
int num1=,num2=,num3=;
for(int i=;i<;i++)
{
if((in[i]||out[i]) && p[i]==i) cnt++;
if(in[i]!=out[i])
{
if(out[i]-in[i]==) {start=i;num1++;}
else if(out[i]-in[i]==-) num2++;
else num3++;
}
} if(!num3 && ((num1== && num2==) || (num1== && num2==)) && cnt==)
{
Fleury(start);
cout<<str[sta.top()]; sta.pop();
while(!sta.empty())
{
cout<<"."<<str[sta.top()];
sta.pop();
}
cout<<endl;
}
else {puts("***");continue;}
}
}

最新文章

  1. 算法(第4版)-1.5 案例研究:union-find算法
  2. 译文---C#堆VS栈(Part Four)
  3. shell判断文件或者文件夹是否存在
  4. C# 图片盖章功能实现,支持拖拽-旋转-放缩-保存
  5. 怎么打开Windows Server 2008 图片预览的功能?
  6. android 40 Io编程
  7. zookeeper 手动T掉已挂节点
  8. BZOJ 2716 Violet 3 天使玩偶 CDQ分治
  9. jquery的slideUp、slideDown、slideToggle等涉及滑动效果的一系列函数,在IE浏览器下有几处bug
  10. 将自己apk打包进其他apk安装思路
  11. html5中的全局属性
  12. 《PHP内核剖析 - 变量/内存管理》
  13. 基于Eureka的服务治理
  14. 打开对话框opendialog
  15. python day09--定义函数
  16. 【LOJ】#2534. 「CQOI2018」异或序列
  17. Sqoop导入HBase,并借助Coprocessor协处理器同步索引到ES
  18. 利用Py-Socket模块做的一个不登陆windows服务器自动实现替换或者调用自动拨号功能
  19. scrapy的简单使用
  20. Windows的图形设备接口与Windows绘图

热门文章

  1. luogu P1379 八数码难题(A*算法入门详细讲解)
  2. 如何获取e.printStackTrace()的内容
  3. Oracle存储过程--案例
  4. [ASP.NET 大牛之路]02 - C#高级知识点概要(1) - 委托和事件
  5. LinearLayout学习笔记
  6. Code Forces 652C Foe Pairs
  7. LaTeX:Question &amp; Answer
  8. 转!!CMPP 网关错误码说明
  9. mysql 数据操作 单表查询
  10. Java压缩多个文件并导出