描述
给你一些单词，请你判断能否把它们首尾串起来串成一串。
前一个单词的结尾应该与下一个单词的道字母相同。
输入
第一行是一个整数N(0<N<20)，表示测试数据的组数
每组测试数据的第一行是一个整数M,表示该组测试数据中有M(2<M<1000)个互不相同的单词，随后的M行，每行是一个长度不超过30的单词,单词全部由小写字母组成。
输出
如果存在拼接方案，请输出所有拼接方案中字典序最小的方案。(两个单词之间输出一个英文句号”.”)
如果不存在拼接方案，则输出
样例输入
1
2
3
4
5
6
7
8
9
10
11
12
| 2
6
aloha
arachnid
dog
gopher
rat
tiger
3
oak
maple
elm
|
样例输出
1
2
| aloha.arachnid.dog.gopher.rat.tiger
***
|
参考答案
Java版
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
| import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;
import java.util.Stack;
class Node {
Queue<String> queue = new PriorityQueue<String>();
}
public class Main {
public static final int LEN = 26;
private int start;
private int[] father, num, inDegree, outDegree;
private Node[] nodes;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int t, n;
Main main;
String str;
Node[] nodes = new Node[LEN];
for (int i = 0; i < LEN; i++) {
nodes[i] = new Node();
}
t = sc.nextInt();
while (t-- != 0) {
n = sc.nextInt();
for (int i = 0; i < n; i++) {
str = sc.next();
nodes[str.charAt(0) - 'a'].queue.add(str);
}
main = new Main(nodes);
main.execute();
for (int i = 0; i < LEN; i++) {
nodes[i].queue.clear();
}
}
sc.close();
}
public Main(Node[] nodes) {
this.nodes = nodes;
father = new int[LEN];
num = new int[LEN];
inDegree = new int[LEN];
outDegree = new int[LEN];
for (int i = 0; i < LEN; i++) {
father[i] = i;
num[i] = 1;
}
for (int i = 0, start, end; i < LEN; i++) {
for (String str : nodes[i].queue) {
start = str.charAt(0) - 'a';
end = str.charAt(str.length() - 1) - 'a';
inDegree[end]++;
outDegree[start]++;
start = find(start);
end = find(end);
if (start != end) {
union(start, end);
}
}
}
}
private int find(int i) {
return i == father[i] ? i : find(father[i]);
}
private void union(int i, int j) {
father[i] = j;
}
private boolean isEularRoute() {
start = -1;
int count = 0;
boolean find = false;
for (int i = 0; i < LEN; i++) {
if (inDegree[i] != outDegree[i]) {
if (Math.abs(inDegree[i] - outDegree[i]) != 1)
return false;
if (!find && inDegree[i] < outDegree[i]) {
find = true;
start = i;
}
if (++count > 2)
return false;
} else if (outDegree[i] > 0 && start == -1) {
start = i;
}
}
return true;
}
private boolean isConnected() {
for (int i = 0, count = 0; i < LEN; i++) {
if (outDegree[i] > 0 && father[i] == i) {
if (++count > 1) {
return false;
}
}
}
return true;
}
private void printResult(int i) {
dfs(i);
if (!stack.isEmpty())
System.out.print(stack.pop());
while (!stack.isEmpty()) {
System.out.print("." + stack.pop());
}
System.out.println();
}
Stack<String> stack = new Stack<String>();
private void dfs(int i) {
while (!nodes[i].queue.isEmpty()) {
String str = nodes[i].queue.poll();
dfs(str.charAt(str.length() - 1) - 'a');
stack.push(str);
}
}
public void execute() {
if (!isConnected() || !isEularRoute()) {
System.out.println("***");
return;
}
printResult(start);
}
}
|