Catenyms
| Time Limit: 1000MS | Memory Limit: 65536K | |
| Total Submissions: 8368 | Accepted: 2202 |
Description
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 last 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
***
用DFS实现的
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <math.h>
#include <vector>
#include <stack>
#include <map>
using namespace std;
#define ll long long int
#define INF 5100000
string a[];
int v[];
vector<pair<int,int> >aa[];
vector<int>ab;
int p[];
int d1[];
int d2[];
int find(int x)
{
while(x!=p[x])
x=p[x];
return x;
}
void fun(int x,int eid)
{
for(int i=; i<aa[x].size(); i++)
if(!v[aa[x][i].second])
{
v[aa[x][i].second]=true;
fun(aa[x][i].first,aa[x][i].second);
}
if(eid>)ab.push_back(eid);
}
int main()
{
int tt;
int i,j;
cin>>tt;
for(i=; i<tt; i++)
{
int n;
cin>>n;
memset(d1,,sizeof(d1));
memset(d2,,sizeof(d2));
for(j=; j<; j++)
p[j]=j,aa[j].clear();
for(j=; j<=n; j++)
{
cin>>a[j];
}
sort(a+,a+n+);
for(j=; j<=n; j++)
{
int x=a[j][]-'a'+;
int y=a[j][a[j].length()-]-'a'+;
d1[x]++;
d2[y]++;
aa[x].push_back(make_pair(y,j));
int fx=find(x);
int fy=find(y);
if(fy!=fx)
p[fy]=fx;
}
int sum=;
int start=a[][]-'a'+;
for(j=; j<; j++)
{
if(d1[j]==&&d2[j]==)continue;
if(p[j]==j)sum++;
}
if(sum>)
cout<<"***"<<endl;
else
{
int dd1=,dd2=;
for(j=; j<; j++)
{
if(d1[j]!=d2[j])
{
if(d1[j]-d2[j]==)
dd1++,start=j;
else if(d2[j]-d1[j]==)
dd2++;
else
{
dd2=;
break;
}
}
}
if(dd2<=&&dd1<=)
{
memset(v,,sizeof(v));
ab.clear();
fun(start,);
for( j=ab.size()-; j>=; j--)
{
cout<<a[ab[j]];
if(j!=)cout<<".";
else cout<<"\n";
} }
else cout<<"***"<<endl;
}
}
}