每个单词可以看做一条边，每个字母就是顶点。
有向图欧拉回路的判定，首先判断入度和出度，其实这个题判定的是欧拉通路，不一定非得构成环，所以可以有一个点的顶点入度比出度大1，另外一个点的出度比入度大1，或者每个点的出度和入度相等。用并查集判断是否弱联通。最后dfs求出欧拉路径，不过这个题是让求字典序最小的那个，所以加边之前先把边排序。
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <string> using namespace std; const int maxn = 1100; struct Edge { int to, next; int id; }edge[maxn * 2]; int tot, head[maxn]; int in[maxn], out[maxn]; int F[maxn]; int st; bool vis[30]; string str[maxn]; void init() { tot = 0; memset(head, -1, sizeof(head)); memset(F, -1, sizeof(F)); } void addedge(int u, int v, int id) { edge[tot].to = v; edge[tot].next = head[u]; edge[tot].id = id; head[u] = tot++; } int Find(int x) { if (F[x] == -1) return x; return F[x] = Find(F[x]); } void Union(int x, int y) { int tx = Find(x); int ty = Find(y); if (tx != ty) F[tx] = ty; } bool check(int s) { int in1 = 0, out1 = 0; for (int i = 1; i <= 26; i++)//判断出入度关系 { if (in[i] == out[i]) continue; else if (in[i] - out[i] == 1) in1++; else if (out[i] - in[i] == 1) out1++, st = i;//如果有出度比入度大1的，说明是欧拉通路，起点只能是那个出度比入度大1的那个点 else return false; } //printf("in1 = %d, out1 = %d ", in1, out1); if (!(in1 == 1 && out1 == 1) && !(in1 == 0 && out1 == 0)) return false; for (int i = 1; i <= 26; i++)//判断弱联通 if (vis[i] && Find(i) != Find(s)) return false; return true; } bool vis2[maxn * 2];//判断每条边是否访问过。 int top; int ans[maxn * 2];//保存路径 void dfs(int u) { for (int i = head[u]; i != -1; i = edge[i].next) { if (!vis2[i]) { vis2[i] = true; dfs(edge[i].to); ans[top++] = i; } } } int main() { int T, n; scanf("%d", &T); while (T--) { init(); scanf("%d", &n); memset(in, 0, sizeof(in)); memset(out, 0, sizeof(out)); memset(vis, false, sizeof(vis)); int u, v; st = 10000; for (int i = 0; i <n; i++) cin >> str[i]; sort(str, str + n);//从小到大排序 for (int i = n - 1; i >= 0; i--)//因为链式前向星是逆序存图，所以反过来从大到小读入。 { u = str[i][0] - 'a' + 1; v = str[i][str[i].length() - 1] - 'a' + 1; vis[u] = vis[v] = true; addedge(u, v, i); ++in[v]; ++out[u]; Union(u, v); st = min(st, min(u, v));//找出最小的那个点来 } if (!check(st)) puts("***"); else { top = 0; memset(vis2, false, sizeof(vis2)); dfs(st); for (int i = top - 1; i > 0; i--) cout << str[edge[ans[i]].id] << "."; cout << str[edge[ans[0]].id] << endl; } } return 0; }