描述
给你一些单词,请你判断能否把它们首尾串起来串成一串。
前一个单词的结尾应该与下一个单词的道字母相同。
如
aloha
dog
arachnid
gopher
tiger
rat
可以拼接成:aloha.arachnid.dog.gopher.rat.tiger
输入
第一行是一个整数N(0<N<20),表示测试数据的组数
每组测试数据的第一行是一个整数M,表示该组测试数据中有M(2<M<1000)个互不相同的单词,随后的M行,每行是一个长度不超过30的单词,单词全部由小写字母组成。
输出
如果存在拼接方案,请输出所有拼接方案中字典序最小的方案。(两个单词之间输出一个英文句号".")
如果不存在拼接方案,则输出
***
样例输入
2
6
aloha
arachnid
dog
gopher
rat
tiger
3
oak
maple
elm
样例输出
aloha.arachnid.dog.gopher.rat.tiger
***
题意:给你一些单词问你这些单词是否可以首尾相连,如果可以则输出相应的顺序。
思路:构建有向图,先判断该图中是否存在欧拉回路或者欧拉通路,如果存在,则dfs满足条件的结果。
AC代码:
#include<iostream>
#include<string>
#include<algorithm>
#include<string.h>
#include<cstdio>
#define CLR(arr,value) memset(arr,0,sizeof(arr));
#define N 1001
#define M 26
using namespace std;
struct node
{
int s;
int e;
char s1[31];
bool vis;
};
typedef struct node Node;
Node map[N];
bool visit[M];
int in[M];
int out[M];
int Father[M];
int Ran[N];
int p[N];
bool flag;
int n;
void init()
{
memset(visit,false,sizeof(visit));
CLR(in,0);
CLR(out,0);
CLR(p,0);
CLR(Ran,0);
for(int i=0;i<M;++i) Father[i]=i;
}
bool operator < (node const& x,node const&x1)
{
return strcmp(x.s1,x1.s1)<0;
}
int Find(int x)
{
if(x==Father[x]) return x;
else return Father[x]=Find(Father[x]);
}
void Union(int a,int b)
{
int x=Find(a);
int y=Find(b);
if(x!=y) Father[x]=y;
}
bool is_connect()
{
int cnt=0;
for(int i=0;i<M;++i)
if(visit[i]&&Father[i]==i) cnt++;
return cnt==1;
}
bool is_Euler()
{
int res=0;
for(int i=0;i<M;++i)
if(visit[i]&&out[i]!=in[i]) p[res++]=out[i]-in[i];
return (res==0||(res==2&&p[0]*p[1]==-1));
}
void dfs(int now,int _e,int cur)
{
if(flag) return;
for(int i=0;i!=n;++i)
{
if(!map[i].vis&&_e==map[i].s)
{
Ran[cur-1]=now;
if(cur+1==n)
{
flag=true;
Ran[cur]=i;
return;
}
map[i].vis=true;
dfs(i,map[i].e,cur+1);
map[i].vis=false;
}
}
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
init();
for(int i=0;i!=n;++i)
{
scanf("%s",map[i].s1);
map[i].s=map[i].s1[0]-'a';
map[i].e=map[i].s1[strlen(map[i].s1)-1]-'a';
map[i].vis=false;
Union(map[i].s,map[i].e);
out[map[i].s]++;
in[map[i].e]++;
visit[map[i].s]=true;
visit[map[i].e]=true;
}
if(is_connect()&&is_Euler())
{
std::sort(map,map+n);
flag=false;
for(int i=0;i!=n;++i)
{
map[i].vis=true;
dfs(i,map[i].e,1);
map[i].vis=false;
}
for(int i=0;i!=n-1;++i) printf("%s.",map[Ran[i]].s1);
printf("%s",map[Ran[n-1]].s1);
printf("\n");
}
else printf("***\n");
}return 0;
}
分享到:
相关推荐
动态规划:http://acm.zju.edu.cn/forum/viewtopic.php?t=69 搜索:http://acm.zju.edu.cn/forum/viewtopic.php?t=67 数论:http://acm.zju.edu.cn/forum/viewtopic.php?t=66 几何:...
ACM大量习题题库 现在网上有许多题库,大多是可以在线评测,所以叫做Online Judge。除了USACO是为IOI准备外,其余几乎全 部是大学的ACM竞赛题库。 USACO http://ace.delos.com/usacogate 美国著名在线题库,专门为...
浙江大学在线题库:http://acm.zju.edu.cn/problems.php 浙江工业大学在线题库:http://acm.zjut.edu.cn 衡阳市第八中学信息学奥赛论坛&zju译题站:http://61.187.179.132:82/ UVA在线题库:...
In this problem, you are asked to implement this. The following commands need to be supported: BACK: Push the current page on the top of the forward stack. Pop the page from the top of the backward...
(我现在主要在CSDN上整理计算机安全、软件工程(可信软件)、系统及通信方面的论文及相关理论书籍,如果对这方面内容感兴趣,可以访问:http://qysh123.download.csdn.net/ 查看我上传的所有资料。内容比较多,需要...
http://blog.csdn.net/acmmmm
TagRec won the best poster award @ Hypertext 2014 (HT'14) conference: http://ht.acm.org/ht2014/index.php?awards.poster TagRec is also a main part of the recommender systems in the Layers project ...
zju 1048 Financial Managementhttp://acm.zju.edu.cn/show_problem.php?pid=1048
:로풀어보기: ://www.acmicpc.net/step 방온라인SDS방온라인스터디: ://www.acmicpc.net/group/workbook/list/9962 본반기본반: ://www.acmicpc.net/workbook/view/2047 고득점로그래머스고득점工具包: ://...
(我现在主要在CSDN上整理计算机安全、软件工程(可信软件)、系统及通信方面的论文及相关理论书籍,如果对这方面内容感兴趣,可以访问:http://qysh123.download.csdn.net/ 查看我上传的所有资料。内容比较多,需要...
3、林杰博客说明:http://linjie.org/2015/08/06/amr%E6%A0%BC%E5%BC%8F%E8%BD%ACmp3%E6%A0%BC%E5%BC%8F-%E5%AE%8C%E7%BE%8E%E8%A7%A3%E5%86%B3Linux%E4%B8%8B%E8%BD%AC%E6%8D%A20K%E9%97%AE%E9%A2%98/
本资源包括项目演示视频、源代码、说明文档、项目资源。 本场景是一个篮球场,篮球可以做自由落体运动和反弹。 场景涉及灯光,纹理,摄像...具体细节可看博客:https://blog.csdn.net/A_ACM/article/details/100569142
湖南大学ACM-OJ的部分题目代码,对学习数据结构和算法很有帮助
題目: http://acm.pku.edu.cn/JudgeOnline/problem?id=2418
百柱在线裁判 문제on관리관기저장소입니다。 1일1커밋용 Python목적 Python및리알고
训练赛网址https://acm.zcmu.edu.cn/JudgeOnline/contest.php?cid=1343
算法
pascal source code for http://acm.pku.edu.cn/JudgeOnline/problem?id=3728
zju 1025 Wooden Sticks http://acm.zju.edu.cn/show_problem.php?pid=1025