`
tulunta
  • 浏览: 356871 次
文章分类
社区版块
存档分类
最新评论

http://acm.nyist.net/JudgeOnline/problem.php?pid=99&&单词拼接

 
阅读更多
描述

给你一些单词,请你判断能否把它们首尾串起来串成一串。

前一个单词的结尾应该与下一个单词的道字母相同。

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;
}    


分享到:
评论

相关推荐

    浙大ACM分类抽象结构

    动态规划: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练习题库

    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在线题库:...

    Web Navigation

    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...

    PLDI 2011-ACM SIGPLAN conference on PLDI 2011

    (我现在主要在CSDN上整理计算机安全、软件工程(可信软件)、系统及通信方面的论文及相关理论书籍,如果对这方面内容感兴趣,可以访问:http://qysh123.download.csdn.net/ 查看我上传的所有资料。内容比较多,需要...

    九野的模版3.15.10.pdf

    http://blog.csdn.net/acmmmm

    Android代码-TagRec

    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 ...

    zju1048.rar_acm.zju.edu._pid_show_zju acm

    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 고득점로그래머스고득점工具包: ://...

    ICSE 2011-International Conference on Software Engineering

    (我现在主要在CSDN上整理计算机安全、软件工程(可信软件)、系统及通信方面的论文及相关理论书籍,如果对这方面内容感兴趣,可以访问:http://qysh123.download.csdn.net/ 查看我上传的所有资料。内容比较多,需要...

    完美解决Jave在linux下转为MP3时为0字节或其他异常

    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/

    OpenGL-篮球场.rar

    本资源包括项目演示视频、源代码、说明文档、项目资源。 本场景是一个篮球场,篮球可以做自由落体运动和反弹。 场景涉及灯光,纹理,摄像...具体细节可看博客:https://blog.csdn.net/A_ACM/article/details/100569142

    HN_OJ.rar_http://acm.hn_hunan oj_oj_湖南大学oj_湖南大学oj网

    湖南大学ACM-OJ的部分题目代码,对学习数据结构和算法很有帮助

    [PKU] 2418 Hardwood Species

    題目: http://acm.pku.edu.cn/JudgeOnline/problem?id=2418

    Baekjoon-Online-Judge:https://www.acmicpc.net

    百柱在线裁判 문제on관리관기저장소입니다。 1일1커밋용 Python목적 Python및리알고

    程序设计阶段性测试 题解.pdf

    训练赛网址https://acm.zcmu.edu.cn/JudgeOnline/contest.php?cid=1343

    算法:https://www.acmicpc.net

    算法

    pku3728.zip_pku 3621 pasc_pku 3728

    pascal source code for http://acm.pku.edu.cn/JudgeOnline/problem?id=3728

    zju1025.rar_ZJU_acm zju 10_pid_sticks_zju 1025

    zju 1025 Wooden Sticks http://acm.zju.edu.cn/show_problem.php?pid=1025

Global site tag (gtag.js) - Google Analytics