1. 从一道题看拓扑排序的本质

1.1 这道题到底在问什么

先把这个标题拆开看。UVA200 和 LA5139 是同一道题在不同题库里的编号，题名叫 Rare Order，直译过来就是“罕见的顺序”。题目的设定非常朴素：考古学家发现了一块石碑，上面刻着一串按某种未知字母表顺序排列的单词，字母表里只有大写字母，而且这个字母表里字母的先后顺序和常规的 A 到 Z 不一样。现在给你这些单词，它们已经按照这个未知字母表的顺序排好了，要求你推断出这个字母表里字母的相对顺序。

举个具体的例子。假设未知字母表里只有 A、B、C、D 四个字母，给你这样一组单词：

XWY XWZ YWW

因为单词是按未知字母表顺序排列的，所以第一个单词和第二个单词之间，前两个字母 XW 相同，第三个字母 Y 和 Z 不同，且第一个单词排在前面，说明在这个未知字母表里 Y 排在 Z 前面。第二个单词和第三个单词之间，第一个字母 X 和 Y 不同，说明 X 排在 Y 前面。综合起来就得到 X < Y < Z 这样一个偏序关系。

这就是整道题的核心：从一组已排序的字符串中，提取出字符之间的偏序关系，再对这个偏序关系做拓扑排序，得到一个合法的全序。

1.2 为什么这题值得单独拿出来讲

很多人第一次看到这道题，第一反应是“直接比较相邻两个单词的第一个不同字符不就行了”。这个直觉方向是对的，但真正动手写的时候会发现坑一个接一个：怎么处理前缀关系、怎么保证拓扑排序结果唯一、怎么处理多个合法解的情况、输入格式怎么读。

这道题之所以经典，是因为它把拓扑排序的建模过程完整地暴露了出来。平时我们做拓扑排序，图是直接给你的，你只需要跑算法。但这道题里，图需要你自己从字符串里“挖”出来。这个“从实际问题抽象成图”的过程，才是真正考验功力的地方。

我个人的经验是，能把这道题从头到尾写对、写干净的人，对拓扑排序的理解基本就到位了。它涉及的知识点包括：字符串相邻比较、偏序关系的提取、有向图的构建、入度统计、拓扑排序的队列实现、以及结果唯一性的判断。每一个环节都有细节。

1.3 适合谁来读这篇内容

如果你正在学图论，刚看完拓扑排序的定义但不知道怎么用，这篇内容适合你。如果你刷题刷到这道题卡住了，不知道从哪下手建图，这篇内容也适合你。如果你已经会写拓扑排序，但想看看别人是怎么处理边界情况的，同样可以看看。

我会从建模思路讲起，然后一步步拆解代码实现，最后把我自己踩过的坑和调试技巧都摊开来说。整篇内容不依赖任何特定题库的提交环境，你用什么语言写都行，思路是通用的。

2. 核心思路拆解与建模过程

2.1 从“已排序”这个条件能榨出什么信息

题目给的关键条件是：这些单词已经按照未知字母表的顺序排好了。这句话的信息量很大。在字典序里，两个字符串比较大小的规则是：从左往右逐位比较，第一个不同的字符决定了两个字符串的大小关系；如果一个字符串是另一个的前缀，那么短的排在前面。

把这个规则反过来用：如果单词 A 排在单词 B 前面，那么要么 A 是 B 的前缀，要么 A 和 B 在某个位置出现了不同的字符，且 A 在这个位置的字符在未知字母表里排在 B 对应字符的前面。

注意，这里有一个非常重要的细节：如果 A 是 B 的前缀，我们无法从这一对单词中得到任何字符之间的顺序信息。因为前缀关系下，字典序的判定不依赖任何字符的相对顺序，只依赖长度。这一点是很多人第一次写会忽略的地方，也是导致建出错误图或者死循环的常见原因。

所以我们的策略是：只比较相邻的两个单词。为什么是相邻？因为如果单词序列已经排好序，那么相邻两个单词之间必然存在一个“最小差异”，这个差异直接反映了某两个字符的顺序关系。非相邻的单词之间的顺序关系，可以通过相邻关系的传递性推导出来，不需要单独提取。

2.2 相邻比较的具体操作

假设相邻两个单词是 s1 和 s2，s1 排在 s2 前面。我们从下标 0 开始，同时遍历两个字符串，找到第一个满足 s1[i] != s2[i] 的位置 i。这时候我们就得到了一条有向边：s1[i] -> s2[i]，表示 s1[i] 这个字符排在 s2[i] 前面。

如果遍历完了其中一个字符串都没有找到不同的字符，说明短的那个是长的那个的前缀，这一对单词不提供任何顺序信息，直接跳过。

这里有一个容易出错的点：遍历的终止条件应该是i < min(s1.length, s2.length)，而不是i < s1.length && i < s2.length。虽然逻辑上等价，但写的时候容易写错。我建议直接用 min 函数，清晰不容易出错。

2.3 为什么用拓扑排序而不是其他方法

提取出来的是一堆“A 在 B 前面”的偏序关系。我们需要把这些偏序关系整合成一个全序，也就是所有出现过的字符的一个排列，使得所有偏序关系都得到满足。这正是拓扑排序要解决的问题。

有人可能会想，能不能用并查集？不行，并查集处理的是等价关系，不是偏序关系。能不能用排序算法？也不行，因为字符之间没有直接的比较函数，你没法写一个 comparator 出来。拓扑排序是唯一自然的选择。

拓扑排序的基本流程是：统计每个节点的入度，把入度为 0 的节点加入队列，然后不断取出队首节点，把它指向的节点入度减一，如果减到 0 就加入队列。最后队列里出来的顺序就是一个合法的拓扑序。

2.4 结果唯一性的判断

题目通常要求输出这个未知字母表的顺序。但这里有一个微妙的地方：如果拓扑排序过程中，队列里同时存在多个入度为 0 的节点，说明存在多个合法的拓扑序，也就是我们无法唯一确定字母表的顺序。

这道题的标准做法是：如果队列中同时有多个节点，我们仍然可以输出其中一个合法的拓扑序，因为题目通常保证有唯一解，或者接受任意合法解。但如果你想严谨一点，可以判断队列的大小是否始终为 1，如果不是，说明解不唯一。

我个人的习惯是：先按标准拓扑排序输出一个合法解，然后在调试阶段检查队列大小，确认题目数据是否保证唯一解。这样既不牺牲性能，又能帮助理解题目性质。

3. 代码实现与关键细节

3.1 数据结构的选择

我们需要存储图。因为字符集只有 26 个大写字母，所以可以用一个 26x26 的邻接矩阵来表示边，或者用邻接表。邻接矩阵的好处是去重方便，因为同一对字符之间可能有多条边（多个相邻单词对给出相同的顺序关系），用矩阵可以直接覆盖，不用额外判重。

入度用一个长度为 26 的数组来统计。另外还需要一个布尔数组来标记哪些字符出现过，因为最后输出的时候只需要输出出现过的字符，没出现过的字符不应该出现在结果里。

队列用标准库的 queue 或者自己用数组模拟都行。我用数组模拟，因为数据量很小，而且方便调试。

3.2 建图过程的代码骨架

#include <bits/stdc++.h> using namespace std; int main() { string s1, s2; bool adj[26][26] = {false}; int indeg[26] = {0}; bool appeared[26] = {false}; // 读入第一个单词 if (!(cin >> s1)) return 0; for (char c : s1) appeared[c - 'A'] = true; while (cin >> s2 && s2 != "#") { for (char c : s2) appeared[c - 'A'] = true; // 比较 s1 和 s2 int len = min(s1.size(), s2.size()); for (int i = 0; i < len; i++) { if (s1[i] != s2[i]) { int u = s1[i] - 'A'; int v = s2[i] - 'A'; if (!adj[u][v]) { adj[u][v] = true; indeg[v]++; } break; } } s1 = s2; } // 拓扑排序 queue<int> q; for (int i = 0; i < 26; i++) { if (appeared[i] && indeg[i] == 0) { q.push(i); } } string result; while (!q.empty()) { int u = q.front(); q.pop(); result += (char)(u + 'A'); for (int v = 0; v < 26; v++) { if (adj[u][v]) { indeg[v]--; if (indeg[v] == 0) { q.push(v); } } } } cout << result << endl; return 0; }

这段代码的核心逻辑就是上面说的：读入、建图、拓扑排序、输出。但有几个地方需要特别注意。

3.3 输入格式的处理

这道题的输入格式比较特殊：多个单词，以单独一行的#作为结束标志。而且可能有多个测试用例，每个用例以#结束。我上面的代码只处理了一个用例，实际写的时候需要在外层再加一层循环。

另外，第一个单词的读入和后续单词的读入要分开处理，因为第一个单词没有前一个单词可以比较。我上面的写法是先读第一个，然后在循环里读后续的，每次比较当前读入的和上一个读入的。

还有一个细节：如果输入中只有一个单词，那么没有任何比较发生，图是空的，所有出现过的字符入度都是 0，拓扑排序会按字母顺序输出它们。这其实是一个合法的解，因为没有任何约束。

3.4 拓扑排序的边界情况

拓扑排序有一个前提：图必须是有向无环图。如果图中有环，拓扑排序会失败，队列会在某个时刻变空但还有节点没有输出。这道题的数据保证不会出现环，因为字母表本身是一个全序，不会出现循环依赖。

但实际写的时候，我还是建议加一个检查：如果最后输出的字符数量小于出现过的字符数量，说明有环，这时候可以输出错误信息或者直接返回。虽然题目保证不会发生，但养成这个习惯对写其他题也有好处。

另一个边界情况是：如果某个字符从未出现在任何单词中，它不应该出现在结果里。我用 appeared 数组来处理这个，只有出现过的字符才会被加入队列。

4. 常见问题与排查技巧实录

4.1 为什么我的答案和标准答案不一样

这是最常见的问题。很多人跑完代码发现输出和样例不一样，就以为自己错了。但实际上，如果题目没有保证唯一解，那么任何合法的拓扑序都是正确答案。

我遇到过好几次，自己输出的顺序和样例不同，但提交上去是 AC 的。后来我养成了一个习惯：写一个检查函数，验证输出的序列是否满足所有提取出来的偏序关系。如果满足，那就是对的，不用管和样例是否一致。

验证的方法很简单：对于每一条边 u -> v，检查 u 在输出序列中的位置是否在 v 前面。如果是，这条边就满足了。所有边都满足，这个拓扑序就是合法的。

4.2 前缀关系导致的错误

前面提到过，如果 s1 是 s2 的前缀，这一对单词不提供任何信息。但很多人写比较循环的时候，会忘记处理这种情况，导致循环结束后还在尝试访问 s1[i] 或 s2[i]，造成越界。

正确的做法是：循环只遍历到 min(s1.size(), s2.size())，如果循环正常结束都没有 break，说明没有找到不同的字符，直接跳过这一对。

还有一种更隐蔽的错误：如果 s1 比 s2 长，且 s1 的前缀是 s2，那么按照字典序，s2 应该排在 s1 前面。但题目给的是 s1 排在 s2 前面，这就矛盾了。不过题目保证输入是合法的，所以这种情况不会出现。但如果你想写一个健壮的版本，可以加一个检查：如果 s1.size() > s2.size() 且 s2 是 s1 的前缀，说明输入有问题。

4.3 重复边的处理

同一对字符之间可能有多条边。比如多个相邻单词对都给出了 A -> B 这个关系。如果不判重，入度会被重复累加，导致拓扑排序出错。

用邻接矩阵的话，加边之前检查一下 adj[u][v] 是否已经是 true，如果是就不再加。用邻接表的话，可以用一个 set 或者手动判重。我推荐用邻接矩阵，因为字符集小，26x26 的布尔数组占不了多少空间，而且判重 O(1)。

4.4 队列中多个节点时的处理

如果拓扑排序过程中队列里同时有多个节点，说明有多个合法的拓扑序。这时候你有两个选择：一是随便取一个，输出一个合法解；二是判断题目是否要求唯一解，如果要求唯一解但队列不唯一，说明数据有问题。

我个人的做法是：先按随便取的方式写，提交看看。如果 WA 了，再考虑是不是唯一性的问题。大多数情况下，题目要么保证唯一解，要么接受任意合法解，不会在这上面卡人。

4.5 调试技巧：打印中间状态

这道题的调试其实很简单，因为数据量小。我通常会在建图完成后，打印出所有的边和入度，然后手动验证一下。比如：

Edge: X -> Y Edge: Y -> Z Indeg: X=0, Y=1, Z=1

这样一眼就能看出图建得对不对。如果边少了或者多了，再回去检查比较逻辑。

拓扑排序过程中，也可以打印每次出队的节点和当前队列的内容，帮助理解排序过程。

5. 从这道题延伸出的通用建模能力

5.1 偏序关系的提取是很多问题的核心

这道题的本质是：从数据中提取偏序关系，然后做拓扑排序。这个模式在很多问题里都会出现。比如课程安排问题，先修课关系就是偏序关系；比如编译原理里的依赖分析，变量之间的依赖也是偏序关系；比如项目管理里的任务调度，任务之间的先后顺序还是偏序关系。

学会从实际问题中提取偏序关系，比学会写拓扑排序代码更重要。因为拓扑排序的代码是固定的，但怎么建图是千变万化的。

5.2 拓扑排序的变体

标准拓扑排序是输出一个合法序列。但实际应用中，可能会有各种变体。比如要求输出字典序最小的拓扑序，这时候把队列换成优先队列就行了。比如要求判断是否有环，只需要检查输出节点数是否等于总节点数。比如要求输出所有拓扑序，那就需要回溯搜索。

这道题用的是最标准的拓扑排序，但理解了标准版本，变体也就容易了。

5.3 字符集小的时候可以用数组代替哈希表

这道题里字符集只有 26 个大写字母，所以用数组比用哈希表方便得多。这是一个通用的技巧：当键的范围很小且连续的时候，直接用数组，不要用 map 或 unordered_map。数组的访问速度更快，代码也更简洁。

我见过很多人一上来就用 map<char, vector > 来建图，其实完全没必要。26 个元素的数组足够了，而且调试的时候直接打印数组内容，一目了然。

6. 我踩过的坑与实操心得

6.1 输入读取的坑

这道题的输入格式是多个单词，以 # 结束。我第一次写的时候，用 getline 读整行，然后按空格分割，结果发现单词之间可能有多个空格，分割起来很麻烦。后来改用 cin >> s，因为 cin 会自动跳过空白字符，读单词非常方便。

但 cin >> s 有一个问题：它不会读入换行符。所以判断 # 的时候，直接比较字符串就行了，不用管换行。

还有一个坑：如果输入中有空行，cin >> s 会自动跳过，不会读到空字符串。这其实是好事，省去了处理空行的麻烦。

6.2 数组初始化的坑

C++ 里局部数组不会自动初始化，必须手动初始化。我一开始忘了把 adj 和 indeg 清零，导致第二个测试用例的结果被第一个测试用例污染。后来养成了习惯：每次处理新测试用例之前，用 memset 或者 fill 把数组清零。

用 memset 的话，注意只能对 POD 类型使用，而且第二个参数是字节值。对于 bool 数组，memset(adj, 0, sizeof(adj)) 是正确的。对于 int 数组，memset(indeg, 0, sizeof(indeg)) 也是正确的。

6.3 输出格式的坑

题目要求输出字母表的顺序，通常是一行字符串。但有些版本的题目可能要求每个字符之间加空格，或者有其他格式要求。我建议先仔细读题，确认输出格式，不要想当然。

另外，如果结果是空字符串（比如输入只有一个 #），要确保程序不会崩溃。我上面的代码在这种情况下会输出空行，这是合理的。

6.4 性能上的考虑

这道题的数据量很小，26 个字符，最多几百个单词，任何合理的实现都能在时限内跑完。所以不需要考虑性能优化，把代码写清楚、写对才是最重要的。

但如果你想练手，可以试试用邻接表代替邻接矩阵，或者用优先队列代替普通队列，看看代码会变成什么样。这些练习对理解数据结构的选择有帮助。

6.5 一个实用的调试模板

我写这类题的时候，通常会加一个 debug 函数，在本地调试时打印中间状态，提交时注释掉。比如：

void debug_print(bool adj[26][26], int indeg[26], bool appeared[26]) { for (int i = 0; i < 26; i++) { if (!appeared[i]) continue; for (int j = 0; j < 26; j++) { if (adj[i][j]) { printf("Edge: %c -> %c\n", i + 'A', j + 'A'); } } } for (int i = 0; i < 26; i++) { if (appeared[i]) { printf("Indeg[%c] = %d\n", i + 'A', indeg[i]); } } }

这个函数在调试的时候非常有用，可以快速确认图建得对不对。我建议每个学拓扑排序的人都准备一个类似的调试工具，遇到问题先打印图，再分析。

7. 从解题到工程：拓扑排序的实际应用

7.1 构建系统里的依赖解析

如果你用过 make、cmake 这类构建工具，它们内部就在做拓扑排序。源文件之间的依赖关系形成一个有向图，构建系统需要找到一个顺序，使得每个文件在被依赖的文件之后编译。这就是拓扑排序的典型应用。

和这道题类似的地方在于：依赖关系需要从配置文件或者源文件的 include 语句中提取出来，然后建图，然后排序。提取的过程和这道题里从字符串提取偏序关系的过程异曲同工。

7.2 任务调度中的顺序安排

项目管理里经常需要安排任务的执行顺序，有些任务必须在其他任务之前完成。这些约束关系形成一个偏序，拓扑排序可以给出一个可行的执行顺序。如果图中有环，说明约束矛盾，项目无法按计划执行。

这道题里的字母表推断，本质上也是一个调度问题：每个字符是一个任务，字符之间的顺序约束是任务之间的依赖，拓扑排序给出一个可行的执行顺序。

7.3 数据库迁移的顺序确定

数据库迁移脚本之间可能有依赖关系，比如某个表必须先创建，另一个表才能引用它。这些依赖关系可以用拓扑排序来确定执行顺序。如果迁移脚本很多，手动排序容易出错，用拓扑排序自动生成顺序就可靠得多。

这个场景和这道题的区别在于：数据库迁移的依赖关系通常是显式声明的，而这道题的依赖关系需要从数据中推断。但核心算法是一样的。

7.4 课程安排问题

这是拓扑排序最经典的应用场景：给定若干课程和它们之间的先修关系，判断是否可以完成所有课程，如果可以，给出一个学习顺序。这道题和课程安排问题的区别在于：课程安排的依赖关系是直接给的，这道题的依赖关系需要从字符串里挖。

但两者的解法完全一样：建图、统计入度、拓扑排序。学会这道题，课程安排问题也就迎刃而解了。

8. 完整代码与测试用例

8.1 完整可运行的代码

#include <bits/stdc++.h> using namespace std; int main() { string s1, s2; while (cin >> s1 && s1 != "#") { bool adj[26][26]; int indeg[26]; bool appeared[26]; memset(adj, 0, sizeof(adj)); memset(indeg, 0, sizeof(indeg)); memset(appeared, 0, sizeof(appeared)); for (char c : s1) appeared[c - 'A'] = true; while (cin >> s2 && s2 != "#") { for (char c : s2) appeared[c - 'A'] = true; int len = min(s1.size(), s2.size()); for (int i = 0; i < len; i++) { if (s1[i] != s2[i]) { int u = s1[i] - 'A'; int v = s2[i] - 'A'; if (!adj[u][v]) { adj[u][v] = true; indeg[v]++; } break; } } s1 = s2; } queue<int> q; for (int i = 0; i < 26; i++) { if (appeared[i] && indeg[i] == 0) { q.push(i); } } string result; while (!q.empty()) { int u = q.front(); q.pop(); result += (char)(u + 'A'); for (int v = 0; v < 26; v++) { if (adj[u][v]) { indeg[v]--; if (indeg[v] == 0) { q.push(v); } } } } cout << result << endl; } return 0; }

这段代码处理了多个测试用例，每个用例以 # 结束。外层循环读入第一个单词，如果读到 # 就结束程序。内层循环读入后续单词，直到读到 #。

8.2 测试用例的设计

我设计了几组测试用例来验证代码的正确性：

第一组，最简单的三个单词：

XWY XWZ YWW #

预期输出：X Y Z W 或者 X Y W Z 等合法拓扑序。因为 X < Y，Y < Z，W 没有约束，所以 W 可以出现在任何位置。

第二组，只有一个单词：

ABC #

预期输出：A B C。因为没有约束，按字母顺序输出。

第三组，有前缀关系：

AB ABC #

预期输出：A B C。因为 AB 是 ABC 的前缀，不提供新信息，但 A、B、C 都出现了，按字母顺序输出。

第四组，多个测试用例：

XWY XWZ # ABC ABD #

预期输出两行，分别是第一个用例和第二个用例的结果。

8.3 验证输出合法性的方法

写一个验证函数，检查输出序列是否满足所有边：

bool validate(string result, bool adj[26][26], bool appeared[26]) { int pos[26]; memset(pos, -1, sizeof(pos)); for (int i = 0; i < result.size(); i++) { pos[result[i] - 'A'] = i; } for (int i = 0; i < 26; i++) { if (!appeared[i]) continue; if (pos[i] == -1) return false; for (int j = 0; j < 26; j++) { if (adj[i][j]) { if (pos[j] == -1) return false; if (pos[i] >= pos[j]) return false; } } } return true; }

这个函数检查每个出现过的字符是否都在结果里，以及每条边是否满足顺序要求。如果都满足，输出就是合法的。

9. 进阶思考：如果题目变得更难

9.1 要求输出字典序最小的拓扑序

如果题目要求输出字典序最小的拓扑序，只需要把普通队列换成优先队列（小顶堆）。每次从队列里取最小的节点，这样得到的拓扑序就是字典序最小的。

这个变体在实际中很有用，比如任务调度时希望编号小的任务优先执行。实现起来只需要改一行代码：把 queue 换成 priority_queue<int, vector , greater >。

9.2 要求判断拓扑序是否唯一

判断拓扑序是否唯一的方法是：在拓扑排序过程中，如果队列的大小始终为 1，那么拓扑序唯一；如果某一时刻队列大小大于 1，那么拓扑序不唯一。

这个判断可以用来验证题目数据是否保证唯一解。如果题目要求输出唯一解但数据不唯一，说明题目有问题。

9.3 要求输出所有拓扑序

如果要求输出所有合法的拓扑序，就需要用回溯搜索。每次从当前入度为 0 的节点中选择一个，递归下去，直到所有节点都被输出。这个变体的时间复杂度是指数级的，只适合数据量很小的情况。

实现的时候需要注意：每次选择一个节点后，要把它指向的节点的入度减一，递归返回后再恢复。这是一个典型的回溯模板。

9.4 字符集扩大到小写字母和数字

如果字符集扩大到小写字母和数字，26 个元素的数组就不够用了。这时候可以用 62 个元素的数组（26 个大写 + 26 个小写 + 10 个数字），或者用 map 来映射字符到下标。

我建议还是用数组，因为 62 也不大。用一个函数把字符映射到 0 到 61 的下标就行了。这样比用 map 方便，速度也快。

10. 写在最后的一些个人体会

这道题我前前后后做了好几遍，每次都有新的收获。第一次做的时候，卡在建图上，不知道怎么从字符串里提取边。第二次做的时候，卡在输入格式上，不知道怎么处理多个测试用例。第三次做的时候，卡在输出唯一性上，纠结为什么答案和样例不一样。

后来我总结出一个规律：拓扑排序的代码本身很简单，难的是建图。而建图的关键在于理解问题的约束条件，把约束条件翻译成边。这道题里，约束条件是“单词已排序”，翻译成边就是“相邻单词第一个不同字符的顺序”。

这个翻译过程需要你对字典序的定义非常清楚，对前缀关系非常敏感。任何一个细节没考虑到，建出来的图就是错的。

另外，这道题也让我意识到：验证答案比生成答案更重要。因为拓扑序可能不唯一，你没法通过对比样例来判断对错。你需要自己写一个验证函数，检查输出是否满足所有约束。这个习惯在写其他题的时候也很有用，尤其是那些答案不唯一的题目。

最后，如果你正在学拓扑排序，我建议你把这道题多写几遍，每次尝试不同的实现方式。比如用邻接表代替邻接矩阵，用优先队列代替普通队列，用 DFS 代替 BFS。每换一种方式，你对拓扑排序的理解就会深一层。