2 shunfurh shunfurh 于 2017.09.10 21:53 提问

Catenyms

A catenym is a pair of words separated by a period such that the last letter of the first word is the same as the first letter of the second. For example, the following are catenyms:

dog.gopher
gopher.rat
rat.tiger
aloha.aloha
arachnid.dog
A compound catenym is a sequence of three or more words separated by periods such that each adjacent pair of words forms a catenym. For example,

aloha.aloha.arachnid.dog.gopher.rat.tiger

Given a dictionary of lower case words, you are to find a compound catenym that contains each of the words exactly once.

Input

The first line of standard input contains t, the number of test cases. Each test case begins with 3 <= n <= 1000 - the number of words in the dictionary. n distinct dictionary words follow; each word is a string of between 1 and 20 lowercase letters on a line by itself.

Output

For each test case, output a line giving the lexicographically least compound catenym that contains each dictionary word exactly once. Output "***" if there is no solution.

Sample Input

2
6
aloha
arachnid
dog
gopher
rat
tiger
3
oak
maple
elm

Sample Output

aloha.arachnid.dog.gopher.rat.tiger


1个回答

caozhy
caozhy   Ds   Rxr 2017.09.27 22:11
已采纳
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
poj Catenyms
Catenyms 
poj1300 Door Man(欧拉回路判定)
题意:给你N个房间以及房间之间的门,且给你初始的房间号M,问你从初始房间走,可不可以经过每个门仅1次,最后到达0号房间.且所有的门都被你走过1次? 思路:将房间当成顶点,门作为边,转化为判断无向图是否存在欧拉回路或者通路。          所有门都被走一遍,所以任何有门的房间都必须是在同一连通分量:即degree不为0的节点所属并查集唯一.(因为允许存在孤立的一点,房间)    
欧拉回路输出路径
Catenyms poj hoj 欧拉回路输出路径
Catenyms
是这个题的复杂版,增加了输出路径的一项 重点: 输出字典序最小的解,可以先对输入进行排序可以保证搜索的时候先进入小的点
Catenyms(欧拉通路)
题目:http://poj.org/problem?id=2337 分析:根据题目的意思可以想到两个方向:①把字符串当做点,两点能形成接龙形式则连一条有向边,这是问题变成求一条点不重复的路且经过每一个点。这就像一个路径覆盖问题,但是图上各种多重边让笔者不知道怎么搞所以放弃这个想法;②把字符串当做边,以26个字母为顶点建图,问题变成求边不重复的路且经过每一条边,显然这是求欧拉通路。 PS:码代码
POJ2337 Catenyms
有向图的欧拉路径+字典序最小
POJ-2337 Catenyms
Catenyms Time Limit: 1000MS   Memory Limit: 65536K       Description A catenym is a pair of words separated by a period such that the last letter of the first word is the
POJ 2337 Catenyms(欧拉路径)
题意:在play on words的基础上增加了按字典序打印字符串。 解题思路:判断是否存在欧拉路径的方式和play on words 的方式一样。判断出度和入度即可,关键是如何按字典序输出欧拉路径,字典序可以先对输入的串进行排序,排序之后倒着输入进去, 最后输出再倒着输出就行了。 问题描述 A catenym is a pair of words separated
poj2337 Catenyms【欧拉图】
题目链接:http://poj.org/problem?id=2337 题意:问你所有的字符串能否首尾相连在一起,如果能,输出字典序最小的那一串东西,否则输出* 解析:对于输入所有字符串先排个序,然后逆序建图,这样就搜的时候就是优先选择字典序小的字符串,然后就是判是否符合题意,搜的时候记录一下结果#include <iostream> #include <algorithm> #include
poj 2337 Catenyms 【欧拉路径】
题目链接:http://poj.org/problem?id=2337题意:给定一些单词,如果一个单词的尾字母与另一个的首字母相同则可以连接。问是否可以每个单词用一次,将所有单词连接,可以则输出字典序最小的序列。代码: (bin 神的板子)#include <stdio.h> #include <ctime> #include <math.h> #include <limits.h> #inclu