词链 - 题目列表

题意

把所有单词各使用一次排成链，使前一个单词末字母等于后一个单词首字母。输出字典序最小的词链，不存在则输出 ***。

思路

把 26 个字母看成点，每个单词看成从首字母到末字母的有向边。“每个单词恰好一次”就变成经过每条边恰好一次的欧拉路。

先检查度数：

欧拉路径恰有一个点 out-in=1、一个点 in-out=1，其余平衡；
欧拉回路所有点入度等于出度，此时从最小的有出边字母开始；
其它情况无解。

每个字母的出边按单词降序保存，尾部就是当前字典序最小的单词。非递归 Hierholzer 不断取尾部边，走不动时回退并把进入该点的单词加入结果。最后反转后序结果。

即使度数合法，图也可能不连通；因此最后还要检查结果是否恰好包含 n 条边。包含不足就输出 ***。

Python 知识

word[0]-97 和 word[-1]-97 把小写字节映射到 0..25。
edges.sort(reverse=True) 配合 pop()，既取得最小边又避免列表头部删除的线性移动。
vertex_stack 与 word_stack 平行维护当前路径，替代可能达到 1000 层的递归。
b".".join(reversed(route)) 直接连接字节单词并输出。
/home/rainboy/mycode/hugo-blog/content/program_language/python/sorting_and_ordering.md：降序保存、尾部弹出模式。
/home/rainboy/mycode/hugo-blog/content/program_language/python/cpp_to_python_pitfalls.md：递归深度和列表删除成本。

代码

python

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
61import sys


def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    words = data[1:n + 1]
    graph = [[] for _ in range(26)]
    indegree = [0] * 26
    outdegree = [0] * 26

    for word in words:
        start, end = word[0] - 97, word[-1] - 97
        graph[start].append(word)
        outdegree[start] += 1
        indegree[end] += 1
    for edges in graph:
        edges.sort(reverse=True)

    starts = []
    ends = []
    for letter in range(26):
        difference = outdegree[letter] - indegree[letter]
        if difference == 1:
            starts.append(letter)
        elif difference == -1:
            ends.append(letter)
        elif difference != 0:
            print("***")
            return

    if len(starts) == len(ends) == 1:
        start = starts[0]
    elif not starts and not ends:
        start = next(letter for letter in range(26) if outdegree[letter])
    else:
        print("***")
        return

    vertex_stack = [start]
    word_stack = []
    route = []
    while vertex_stack:
        node = vertex_stack[-1]
        if graph[node]:
            word = graph[node].pop()
            vertex_stack.append(word[-1] - 97)
            word_stack.append(word)
        else:
            vertex_stack.pop()
            if word_stack:
                route.append(word_stack.pop())

    if len(route) != n:
        print("***")
    else:
        sys.stdout.buffer.write(b".".join(reversed(route)))


if __name__ == "__main__":
    main()

cpp

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/**
 * P1127 词链
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-27 00:00
 * update_at: 2026-07-27 00:00
 */

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1005;

int n;
char words[MAXN][MAXN];
int indeg[26], outdeg[26];
int adj[26][MAXN];   // adj[letter][i] = word index
int adj_cnt[26];
bool used[MAXN];
char ans[MAXN][MAXN];
int ans_cnt;

void dfs(int u) {
    // 遍历所有以字母 u 开头的单词
    for (int i = 0; i < adj_cnt[u]; ++i) {
        int wid = adj[u][i];
        if (used[wid]) continue;
        used[wid] = true;
        int v = words[wid][strlen(words[wid]) - 1] - 'a';
        dfs(v);
        strcpy(ans[++ans_cnt], words[wid]);
    }
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%s", words[i]);
        int len = strlen(words[i]);
        int s = words[i][0] - 'a';
        int e = words[i][len - 1] - 'a';
        ++outdeg[s];
        ++indeg[e];
        adj[s][adj_cnt[s]++] = i;
    }
    // 对每个字母的单词按字典序排序（反序，因为 DFS 是倒序输出的）
    for (int i = 0; i < 26; ++i)
        sort(adj[i], adj[i] + adj_cnt[i], [](int a, int b) {
            return strcmp(words[a], words[b]) > 0;
        });
    // 找起点：出度 = 入度 + 1 的字母
    int start = -1;
    int start_cnt = 0, end_cnt = 0;
    for (int i = 0; i < 26; ++i) {
        int diff = outdeg[i] - indeg[i];
        if (diff == 1) ++start_cnt, start = i;
        else if (diff == -1) ++end_cnt;
        else if (diff != 0) { puts("***"); return 0; }
    }
    if (start_cnt > 1 || end_cnt > 1) { puts("***"); return 0; }
    if (start == -1) { // 欧拉回路，找第一个有出度的字母
        for (int i = 0; i < 26; ++i)
            if (outdeg[i]) { start = i; break; }
    }
    dfs(start);
    if (ans_cnt != n) { puts("***"); return 0; }
    for (int i = ans_cnt; i >= 1; --i)
        printf("%s%c", ans[i], i == 1 ? '\n' : '.');
    return 0;
}

复杂度

排序所有单词需要 $O(n\log n)$ ，Hierholzer 遍历 $O(n)$ ；空间复杂度 $O(n)$ 。

总结

建模的关键是“单词是边，不是点”。度数决定欧拉路起点，有序取边决定字典序，结果边数负责最终连通性检查。

词链

目录

题意

思路

Python 知识

代码

复杂度

总结