\(POJ\) \(2337\) \(Catenyms\)
给出\(n\)个单词，求出最小字典序的头尾连接方案。
有向图欧拉路径 板子题。
把每个单词当做边，头字母和尾字母当做节点，建完跑 有向图欧拉路径 即可。
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;
const int N = 1200, M = N * N;
int n;
int din[N], dout[N];
string s[N];
int ans[N], al;
int st[M];
// 链式前向星
int e[M], h[N], idx, w[M], ne[M];
void add(int a, int b, int c = 0) {
e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}
// 记录边的dfs,要注意记录边和记录点的差别
void dfs(int u) {
for (int i = h[u]; ~i; i = ne[i]) {
if (!st[i]) {
st[i] = 1;
dfs(e[i]);
ans[++al] = w[i];
}
}
}
/*
【代码模板】功能：
检测有向图是否存在欧拉路径：
（1）统计每个节点的入度和出度。
（2）对于存在欧拉路径的有向图，只能有一个节点的出度比入度多1，只能有一个节点的入度比出度多1，其余节点的入度和出度必须相等。
（3）如果存在欧拉路径，这个"多余的"出度的节点将作为路径的起点，而"多余的"入度的节点将作为路径的终点。（一般不关心终点）
如何找出有向图的欧拉路径：
为了找到欧拉路径，可以从起始节点开始进行深度优先搜索，遍历所有的边。如果所有的边都被访问到，说明存在欧拉路径，否则不存在。
*/
int getStart() {
int start = 0, a = 0, b = 0, c = 0;
for (int i = 0; i < 26; i++) { // 枚举每个点,每道题的具体实现可能有差异
if (dout[i] != din[i]) a++; // 出度与入度不一致的数量
if (dout[i] == din[i] + 1) b++, start = i; // 起点数量，记录起点
if (dout[i] == din[i] - 1) c++; // 终点数量
}
if (a && (b != 1 || c != 1)) return -1; // 如果有不一致的，并且不是1个，则没有欧拉路径
// 如果是一个环，也是存在欧拉路径的，但所有点的入度和出度一致，st不会被改写，需要再手找出起点。
// 这里不需要判断!st,因为如果st=0,则dout[st]==0,也需要继续查找
while (!dout[start]) start++;
return start;
}
int main() {
#ifndef ONLINE_JUDGE
freopen("POJ2337.in", "r", stdin);
#endif
int T;
scanf("%d", &T);
while (T--) {
memset(din, 0, sizeof din);
memset(dout, 0, sizeof dout);
memset(h, -1, sizeof h);
idx = 0;
memset(st, 0, sizeof st);
scanf("%d", &n);
for (int i = 1; i <= n; i++) cin >> s[i]; // 第几个字符串
sort(s + 1, s + n + 1); // 字典序，排序由小到大
for (int i = n; i; i--) { // 倒序枚举，就是由大到小
int a = s[i][0] - 'a';
int b = s[i][s[i].size() - 1] - 'a';
din[b]++, dout[a]++;
add(a, b, i);
}
int start = getStart();
if (start == -1) {
printf("***\n");
continue;
}
// 从start开始搜索，找出欧拉路径，是有向图的欧拉路径，不是欧拉回路
al = 0; // 清空路径数组游标，准备开始填充路径
dfs(start);
if (al != n) { // 无法遍历到所有的点
printf("***\n");
continue;
}
// 控制格式输出
for (int i = n; i > 1; i--) {
cout << s[ans[i]];
printf(".");
}
cout << s[ans[1]] << endl;
}
return 0;
}