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 和 s2s1 排在 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; } // 拓扑排序 queueint 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: X0, Y1, Z1这样一眼就能看出图建得对不对。如果边少了或者多了再回去检查比较逻辑。拓扑排序过程中也可以打印每次出队的节点和当前队列的内容帮助理解排序过程。5. 从这道题延伸出的通用建模能力5.1 偏序关系的提取是很多问题的核心这道题的本质是从数据中提取偏序关系然后做拓扑排序。这个模式在很多问题里都会出现。比如课程安排问题先修课关系就是偏序关系比如编译原理里的依赖分析变量之间的依赖也是偏序关系比如项目管理里的任务调度任务之间的先后顺序还是偏序关系。学会从实际问题中提取偏序关系比学会写拓扑排序代码更重要。因为拓扑排序的代码是固定的但怎么建图是千变万化的。5.2 拓扑排序的变体标准拓扑排序是输出一个合法序列。但实际应用中可能会有各种变体。比如要求输出字典序最小的拓扑序这时候把队列换成优先队列就行了。比如要求判断是否有环只需要检查输出节点数是否等于总节点数。比如要求输出所有拓扑序那就需要回溯搜索。这道题用的是最标准的拓扑排序但理解了标准版本变体也就容易了。5.3 字符集小的时候可以用数组代替哈希表这道题里字符集只有 26 个大写字母所以用数组比用哈希表方便得多。这是一个通用的技巧当键的范围很小且连续的时候直接用数组不要用 map 或 unordered_map。数组的访问速度更快代码也更简洁。我见过很多人一上来就用 mapchar, 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; } queueint 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 YY ZW 没有约束所以 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_queueint, vector , greater 。9.2 要求判断拓扑序是否唯一判断拓扑序是否唯一的方法是在拓扑排序过程中如果队列的大小始终为 1那么拓扑序唯一如果某一时刻队列大小大于 1那么拓扑序不唯一。这个判断可以用来验证题目数据是否保证唯一解。如果题目要求输出唯一解但数据不唯一说明题目有问题。9.3 要求输出所有拓扑序如果要求输出所有合法的拓扑序就需要用回溯搜索。每次从当前入度为 0 的节点中选择一个递归下去直到所有节点都被输出。这个变体的时间复杂度是指数级的只适合数据量很小的情况。实现的时候需要注意每次选择一个节点后要把它指向的节点的入度减一递归返回后再恢复。这是一个典型的回溯模板。9.4 字符集扩大到小写字母和数字如果字符集扩大到小写字母和数字26 个元素的数组就不够用了。这时候可以用 62 个元素的数组26 个大写 26 个小写 10 个数字或者用 map 来映射字符到下标。我建议还是用数组因为 62 也不大。用一个函数把字符映射到 0 到 61 的下标就行了。这样比用 map 方便速度也快。10. 写在最后的一些个人体会这道题我前前后后做了好几遍每次都有新的收获。第一次做的时候卡在建图上不知道怎么从字符串里提取边。第二次做的时候卡在输入格式上不知道怎么处理多个测试用例。第三次做的时候卡在输出唯一性上纠结为什么答案和样例不一样。后来我总结出一个规律拓扑排序的代码本身很简单难的是建图。而建图的关键在于理解问题的约束条件把约束条件翻译成边。这道题里约束条件是“单词已排序”翻译成边就是“相邻单词第一个不同字符的顺序”。这个翻译过程需要你对字典序的定义非常清楚对前缀关系非常敏感。任何一个细节没考虑到建出来的图就是错的。另外这道题也让我意识到验证答案比生成答案更重要。因为拓扑序可能不唯一你没法通过对比样例来判断对错。你需要自己写一个验证函数检查输出是否满足所有约束。这个习惯在写其他题的时候也很有用尤其是那些答案不唯一的题目。最后如果你正在学拓扑排序我建议你把这道题多写几遍每次尝试不同的实现方式。比如用邻接表代替邻接矩阵用优先队列代替普通队列用 DFS 代替 BFS。每换一种方式你对拓扑排序的理解就会深一层。
