前面的 最短路 和 最小生成树 都在图上选择边或路径。Codeforces 510C 的图却没有直接出现在输入里：输入是一列已经按某种未知字母表排好的名称，我们要从字符串之间的先后关系反推出字母顺序。

这题把“比较两个字符串”变成“建立一条有向边”，再把所有局部约束合成一个全局顺序。它也是理解拓扑排序很合适的入口。

1. 官方信息与约束

510C · Fox And Names 官方题目 于 2026-09-11 核对：难度 1600，标签为 dfs and similar、graphs、sortings，时间限制 2 秒，内存限制 256 MB。

题目给出 1≤n≤100 个互不相同的名称，每个名称长度为 1 到 100，只含小写英文字母。需要输出 a 到 z 的一种排列，使这些名称在新字母表下保持给定顺序；不存在时输出 Impossible。

约束或要求 对解法的影响
只有 26 个字母 图的顶点数固定为 26
名称长度不超过 100 可以直接逐字符比较相邻名称
输出任意合法字母表 任意拓扑序都可接受
可能无解 要分别识别前缀矛盾与有向环
必须输出全部字母 没出现过的字母也要放进拓扑序

2. 字典序真正提供了哪条信息

比较两个不同字符串 s 和 t 时，从左向右寻找第一个不同位置：

  • 若找到 s[j] != t[j]，因为 s 排在 t 前面，所以必须有 s[j] < t[j]；
  • 若一直没有不同字符，较短字符串必须排在前面。

例如 abcd 排在 abca 前面，前三个字符完全相同，真正产生约束的是最后一位：d 必须在 a 之前。前面的 a、b、c 没有提供新的字母关系。

前缀矛盾不能交给拓扑排序处理

若 abc 排在 ab 前面，无论怎样重排字母都不可能成立。两者没有首个不同字符，因此也不会产生有向边；如果不单独检查长度，后面的拓扑排序会误判为有解。

反过来，ab 排在 abc 前面是合法的，但它不限制任何两个字母的相对顺序。

3. 为什么只比较相邻名称

朴素想法是比较所有名称对，共有 O(n²) 对。数据规模虽小，这样写也未必超时，但会重复制造许多可以由传递性推出的约束，还容易混淆“输入顺序”与“字母顺序”。

只比较相邻名称已经足够。若每一对相邻名称都满足非降字典序，那么由字典序的传递性，整列名称就有序。每对相邻名称的第一个不同字符恰好给出保证这一局部顺序所需的直接约束。

把字母视为顶点。若得到“字母 x 必须在 y 前面”，就建立有向边 x→y。重复约束只保留一条边，避免把 y 的入度重复增加。

下面用一组自拟名称演算：

相邻名称 相同前缀 首个不同位置 新约束
baa，abcd 空 b 与 a b→a
abcd，abca abc d 与 a d→a
abca，cab 空 a 与 c a→c
cab，cad ca b 与 d b→d

这四条边允许 b,d,a,c 依次出现；其他没有受到约束的字母可以插在任意合法位置。

4. 从偏序到完整字母表

有向边只描述“谁必须在谁之前”，这是一组偏序约束。拓扑排序要把偏序扩展成一个包含所有顶点的线性顺序。

本文使用 Kahn 算法：

  1. 统计每个字母的入度；
  2. 把所有入度为 0 的字母放进容器；
  3. 每次取出一个字母加入答案，并删除它发出的边；
  4. 新出现的入度 0 顶点继续入队；
  5. 若最终取出的字母少于 26 个，剩余部分含有有向环。

代码使用小根堆，让当前可选字母中较小的先输出。题目并不要求字典序最小答案，这个选择只让输出稳定，方便调试。

环为什么表示无解

若约束同时包含 a→b 和 b→a，就要求 a 在 b 前面且 b 在 a 前面。更长的环同理：沿环走一圈会推出某个字母必须在自己之前。

Kahn 算法处理完所有能消去的入度 0 顶点后，环内每个顶点仍有来自环内的前驱，因此没有谁能先被取出。答案长度不足 26 就准确检测到了这种矛盾。

5. 正确性证明

引理一：建出的每条边都是必要约束

对相邻名称 s,t，若首个不同字符为 s[j]=x、t[j]=y，前面字符完全相同。要让 s 排在 t 前面，只能让 x 在字母表中早于 y，所以边 x→y 必须满足。若不存在不同字符而 s 更长，t 是 s 的真前缀，任何字母顺序都无法改变较短前缀应先出现的规则，因此无解判断正确。

引理二：任意拓扑序都满足所有相邻名称关系

拓扑序保证每条边的起点出现在终点之前。每对有首个不同字符的相邻名称所需约束都已建边，所以该位置会让前一个名称更小；合法前缀对则天然有序。因此所有相邻名称在输出字母表下都有序。

引理三：若 Kahn 算法输出 26 个字母，输出是合法完整字母表

算法只在顶点入度为 0 时取出它，此时它没有尚未输出的前驱，因此不会违反任何边。每个字母恰好入队、输出一次；输出 26 个不同字母后得到完整排列。由引理二，输入名称顺序合法。

定理：算法输出合法字母表，当且仅当问题有解

若算法输出排列，引理三说明它合法。若算法输出 Impossible，原因要么是引理一中的前缀矛盾，要么是 Kahn 算法未能处理全部顶点；后者等价于约束图存在有向环，而环不可能被任何线性字母顺序满足。因此算法不会漏掉可行解，也不会输出错误解。

6. 完整 C++17 实现

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
#include <algorithm>
#include <array>
#include <functional>
#include <iostream>
#include <queue>
#include <string>
#include <vector>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<string> names(n);
    for (string& name : names) cin >> name;

    array<array<bool, 26>, 26> edge{};
    array<int, 26> indegree{};

    for (int i = 0; i + 1 < n; ++i) {
        const string& first = names[i];
        const string& second = names[i + 1];
        int common = 0;
        const int limit = static_cast<int>(min(first.size(), second.size()));
        while (common < limit && first[common] == second[common]) ++common;

        if (common == limit) {
            if (first.size() > second.size()) {
                cout << "Impossible\n";
                return 0;
            }
            continue;
        }

        int from = first[common] - 'a';
        int to = second[common] - 'a';
        if (!edge[from][to]) {
            edge[from][to] = true;
            ++indegree[to];
        }
    }

    priority_queue<int, vector<int>, greater<int>> ready;
    for (int letter = 0; letter < 26; ++letter) {
        if (indegree[letter] == 0) ready.push(letter);
    }

    string order;
    while (!ready.empty()) {
        int from = ready.top();
        ready.pop();
        order.push_back(static_cast<char>('a' + from));

        for (int to = 0; to < 26; ++to) {
            if (edge[from][to] && --indegree[to] == 0) ready.push(to);
        }
    }

    if (order.size() != 26) cout << "Impossible\n";
    else cout << order << '\n';
}

设所有名称的总字符数为 S。比较相邻名称共需 O(S)；图只有 26 个顶点和至多 26² 条边，拓扑排序为 O(26² + 26 log 26)。总时间可写为 O(S+26²)，空间为 O(26²+S)，其中 S 来自保存输入名称。

7. 边界与错误清单

情况 正确处理 常见错误
只有一个名称 任何完整字母排列都合法 误以为至少能得到一条边
ab 在 abc 前 合法且不增加约束 把所有前缀关系判成无解
abc 在 ab 前 立即判无解 因为没有不同字符而忽略
同一约束重复出现 只增加一次入度 重复增入度却只删一次边
有向环 最终输出数少于 26 只构造顺序，不检查数量
某字母从未出现 仍要输出它 只拓扑排序出现过的字母
多个入度 0 字母 任取一个都合法 误以为答案必须唯一

8. 怎样独立验证

验证脚本 tests/verify-fox-names-article.cjs 会提取并无警告编译本文 C++17 代码。对小字母表，它枚举全部字母排列，直接检查是否存在能让名称列表有序的排列；这条参考路径不使用拓扑排序。

脚本还会检查程序输出必须是 26 个不同小写字母，并用输出顺序重新比较所有相邻名称。测试覆盖官方样例、合法前缀、非法前缀、重复边、有向环、没有约束的列表和固定种子随机名称。

掌握这题后，遇到“课程先修”“任务依赖”“未知字符顺序”时，可以先问：输入能否转成 x 必须早于 y 的有向边？接着区分两件事——局部数据本身是否已矛盾，以及整个约束图是否存在环。