2013-12-11 07:51:46Morris
[UVA] 10441 - Catenyms
Problem C: 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.dogA 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.tigerGiven a dictionary of lower case words, you are to find a compound catenym that contains each of the words exactly once. 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. 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
Output for Sample Input
aloha.arachnid.dog.gopher.rat.tiger ***
題目描述：
找一條字典順序最小的，且每個單詞恰好經過一次。
題目解法：用 dfs 找尤拉路徑或尤拉環道。
#include <stdio.h>
#include <string.h>
#include <map>
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>
using namespace std;
struct edge {
int to, e, used;
edge(int a=0, int b=0, int c=0):
to(a), e(b), used(c) {
}
};
vector<edge> g[26];
vector<int> path;
int indeg[26], outdeg[26];
void dfs(int nd) {
int i;
for(i = 0; i < g[nd].size(); i++) {
edge &e = g[nd][i];
if(e.used == 0) {
e.used = 1;
dfs(e.to);
path.push_back(e.e);
}
}
}
string dictionary[1005];
char s[1005][105];
int main() {
int testcase, n;
int i, j, k;
scanf("%d", &testcase);
while(testcase--) {
scanf("%d", &n);
memset(indeg, 0, sizeof(indeg));
memset(outdeg, 0, sizeof(outdeg));
path.clear();
for(i = 0; i < 26; i++)
g[i].clear();
for(i = 0; i < n; i++) {
cin >> dictionary[i];
}
sort(dictionary, dictionary+n);
for(i = 0; i < n; i++) {
int len = dictionary[i].length();
int x = dictionary[i][0] - 'a';
int y = dictionary[i][len-1] - 'a';
outdeg[x]++, indeg[y]++;
g[x].push_back(edge(y, i, 0));
}
int a = 0, b = 0, c = 0;
for(i = 0; i < 26; i++) {
if(indeg[i] == outdeg[i]-1)
a++;
else if(indeg[i] == outdeg[i]+1)
b++;
else if(indeg[i] != outdeg[i])
c++;
}
if(c) {
puts("***");
continue;
}
int rflag = 0;
for(i = 0; i < 26; i++) {
if(indeg[i] == outdeg[i]-1) {
dfs(i);
rflag = 1;
break;
}
}
if(rflag == 0) {
for(i = 0; i < 26; i++) {
if(outdeg[i]) {
dfs(i);
break;
}
}
}
if(path.size() != n )
puts("***");
else {
for(i = path.size()-1; i >= 0; i--) {
int idx = path[i];
cout << dictionary[idx];
if(i) putchar('.');
}
puts("");
}
}
return 0;
}