单词拼接
时间限制：3000 ms | 内存限制：65535 KB
难度：5
- 描述
-
给你一些单词，请你判断能否把它们首尾串起来串成一串。
前一个单词的结尾应该与下一个单词的道字母相同。
如
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
***
如果满足题意，那么数据一定可以构成欧拉回路或者欧拉路径，欧拉回路的条件是： 所有点的入度和出度相等；欧拉路径的条件是：满足欧拉回路条件或者图中最多有一个点入度比出度大1，至多有一个点出度比入度大一，如果满足以上条件，再进行dfs深搜找出一条路径，然后输出，如果找不到则不存在
#include<stdio.h>
#include<algorithm>
#include<utility>
#include<vector>
#include<string.h>
#include<string>
#include<stack>
using namespace std;
vector<pair<string, bool> > v[26];
int agree_in[26];
int agree_out[26];
int m;
int total;
stack<string> stack_str;
int dfs(string word)
{
char ch;
ch = word.at(word.length() - 1);
vector<pair<string, bool> >::iterator i;
if(v[ch - 'a'].size() == 0)
return 0;
for(i = v[ch - 'a'].begin(); i != v[ch - 'a'].end(); i++)
{ if((*i).second == 0)
{
(*i).second = 1;
total++;
if(total == m || dfs((*i).first) == 1)
{
stack_str.push((*i).first);
return 1;
}
(*i).second = 0;
total--;
}
}
return 0;
}
int main()
{
int n;
scanf("%d", &n);
char str[30];
int len;
pair<string, bool> p;
while(n--)
{
scanf("%d", &m);
total = 0;
memset(agree_in, 0, sizeof(agree_in));
memset(agree_out, 0, sizeof(agree_out));
int i;
for(i = 0; i < m ; i++)
{
scanf("%s", &str);
string new_str = str;
p.first = str;
p.second = 0;
v[str[0] - 'a'].push_back(p);
agree_in[str[0] - 'a'] ++;
len = strlen(str);
agree_out[str[len - 1] - 'a'] ++;
}
bool in_flag = 0, out_flag = 0;
bool flag = 0;
int start = -1;
for(i = 0; i < 26 && flag == 0 ; i++)
{
switch(agree_in[i] - agree_out[i])
{
case 1:
if(in_flag == 1)
{
flag =1;
break;
}
start = i;
in_flag = 1;
break;
case -1:
if(out_flag == 1)
{
flag = 1;
break;
}
out_flag = 1;
break;
case 0:
break;
default:
flag = 1;
}
}
if(flag == 1)
{
printf("***\n");
while(!stack_str.empty())
stack_str.pop();
for(i = 0; i < 26; i++)
{
v[i].clear();
}
continue;
}
for(i = 0; i < 26; i++)
{
sort(v[i].begin(), v[i].end());
}
if(start == -1)
{
for(i = 0; i < 26; i++)
{
if(v[i].size() != 0)
{
start = i;
break;
}
}
}
vector<pair<string, bool> >::iterator k;
for(k = v[start].begin(); k != v[start].end(); k++)
{
(*k).second = 1;
total ++;
if( dfs((*k).first) == 1)
{
stack_str.push((*k).first);
break;
}
(*k).second = 0;
total --;
}
if(k == v[start].end())
{
printf("***\n");
while(!stack_str.empty())
stack_str.pop();
}
else
{
printf("%s", stack_str.top().c_str());
stack_str.pop();
while(!stack_str.empty())
{
printf(".%s", stack_str.top().c_str());
stack_str.pop();
}
printf("\n");
}
for(i = 0; i < 26; i++)
{
v[i].clear();
}
}
return 0;
}