说实话看到“安排业务先后顺序”这个标题的时候我第一反应是这不就是个排序题吗按编号排、按优先级排、按时间排……直到把题面真正读进去才发现完全不是这么回事。这是2026年小米春招3月14日场的第二题考的是有向图拓扑排序而且带着两个很实际的要求输出合法的执行顺序以及当存在多种合法顺序时输出字典序最小的那一个。整道题其实就是把“任务调度”“课程修读顺序”这类经典问题披了一层业务外衣解法完全相通。我在整理这套题的时候用Java、C、Python各写了一遍也在常见的OJ输入输出模式下反复测了几轮下面把题目还原、破题思路、三种语言的实现差异以及在线测试中特别容易踩的坑一次性梳理清楚。刷过“课程表”或者“编译依赖”这类题目的朋友看这篇会非常快刚接触图论的同学跟着一步步走也能跑通整道题。1. 还原题目依赖关系到底长什么样1.1 一个被各种转述“污染”的题面春招题库里这道题流传的版本比较杂不同渠道转述的细节不一致有的强调输出字典序最小有的根本没提有的编号从1开始有的从0开始。我把最有代表性、也是最全的一个版本整理成下面这样有 n 个业务编号 1 到 n需要安排一个执行顺序。给出 m 条依赖关系每条关系为 (a, b)表示业务 a 必须在业务 b 开始之前完成。请输出一个合法的执行顺序如果存在多个合法顺序输出字典序最小的一个如果存在循环依赖导致无法安排出任何顺序输出 -1。如果线上版本没有字典序要求处理起来更简单——把优先队列换成普通队列就行其余逻辑完全一样。这里按最全的版本展开是因为它同时覆盖了拓扑排序、环检测和贪心选择三个考察点一道题能讲出三道题的量。1.2 把“先后”翻译成图每个业务都是一个节点拿到这类题第一件事不是想怎么排序而是怎么建模。我习惯先把业务关系画成一张有向图每个业务是一个节点编号就是节点编号一条依赖关系“a 在 b 之前”就是一条从 a 指向 b 的有向边每个节点维护一个入度入度表示“还有多少个前置业务没有完成”。入度为 0 的节点意味着它没有任何前置依赖一开始就可以执行。入度为 2 的节点意味着它前面还压着两个业务必须等那两个都完成它才具备开工条件。举个具体的例子。4 个业务依赖关系是1 在 2 之前3 在 2 之前2 在 4 之前。那么图就是 1→2→4 和 3→2→4。初始状态下1 和 3 的入度都是 02 的入度是 24 的入度是 1。合法的执行顺序可以是 1 3 2 4也可以是 3 1 2 4但字典序最小的那个是 1 3 2 4——因为 1 比 3 小必须先选 1。这就是破题的切入点先建图、统计入度然后用一个集合去维护“当前可以执行”的节点。1.3 为什么循环依赖必然无解很多初学者会问如果业务之间形成了循环依赖比如 1 必须在 2 之前2 又必须在 1 之前是不是只是顺序难找而已不是。这是根本无解。原因很简单环上的每个节点都有自己的前驱没有任何一个节点的入度能变成 0。1 等着 2 完成2 等着 1 完成双方永远在等整个排期就卡死了。拓扑排序只能处理有向无环图DAG一旦检测到环直接输出 -1。在真实项目里这就是典型的排期错误设计评审必须在编码之前编码必须在测试之前某天规则又规定测试必须在设计评审之前那这个项目的交付计划从一开始就是矛盾的。所以环检测不是算法题里才有的概念而是实际项目管理中真会遇到的问题。2. 破题核心Kahn算法配合最小堆2.1 Kahn算法的本质是“模拟可执行队列”拓扑排序最主流的写法是Kahn算法它的思路非常贴合人的直觉一共就三步统计每个节点的入度把所有入度为 0 的节点先放进候选集合从候选集合里取出一个节点 u把 u 加入结果序列遍历 u 的所有后继节点 v把 v 的入度减 1如果 v 的入度变成 0说明 v 的前置业务全部完成把 v 也放进候选集合。循环执行第 2、3 步直到候选集合为空。如果最终结果序列里的节点数等于 n说明所有业务都安排上了如果少于 n说明剩下的节点组成了环输出 -1。你可以把这个过程想象成一个“解锁游戏”一开始只有不需要前置条件的业务亮着你每完成一个就会解锁一批新的业务。入度就是“剩余前置条件数量”每次有任务的前置条件归零它就会被点亮。整个过程不需要回溯不需要搜索因为拓扑排序天然就是按“依赖层次”一层层推进的。2.2 为什么普通队列不够字典序最小这个要求很关键如果没有字典序要求用一个普通队列就能搞定候选集合里先进先出先入队的先执行。可一旦题目要求“多种合法顺序中输出字典序最小”就必须保证每次从候选集合里取出的是所有可执行业务里编号最小的那一个。普通队列做不到这一点因为队列只能按入队顺序出队不能“挑最小”。解决办法是把队列换成最小堆优先队列也就是 Java 里的PriorityQueue、C 里的priority_queue配合greaterint、Python 里的heapq。每次从堆顶弹出编号最小的入度为 0 节点即可。还是上面那个 4 业务的例子。初始入度为 0 的节点有 1 和 3普通队列可能先出 1 也可能先出 3取决于入队顺序但最小堆一定能保证先出 1然后 3 的入度还是 0继续出 3再出 2最后出 4得到 1 3 2 4。这就是字典序最小的严格保障。2.3 复杂度堆版本到底比队列版本慢多少图存储用邻接表每个节点最多入堆一次、出堆一次每条边被扫描一次。纯队列版本的复杂度是 O(n m)n 是节点数m 是边数用了最小堆之后堆的每次插入和弹出都是 O(log n)总复杂度变成 O(n log n m)。m 0 的极端情况没有任何依赖关系下堆版本依然要把 n 个节点全部入堆和出堆所以是 O(n log n)纯队列版本则是 O(n)。如果题目明确不要求字典序数据规模又到了几十万级别用普通队列显然更好但如果题目就是要求字典序堆是必须的没有替代方案。面试时能够主动讲出这个权衡会比单纯背模板高出一个段位。3. Java、C、Python三套实现与差异3.1 JavaPriorityQueue天然就是小顶堆Java 版我用PriorityQueueInteger它默认就是数字升序的小顶堆正好满足字典序需求。邻接表用ListInteger[]数组节点编号从 1 开始所以数组长度开 n 1。import java.util.*; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); int m sc.nextInt(); ListInteger[] graph new List[n 1]; int[] indegree new int[n 1]; for (int i 1; i n; i) { graph[i] new ArrayList(); } for (int i 0; i m; i) { int a sc.nextInt(); int b sc.nextInt(); graph[a].add(b); // a 必须在 b 之前所以 a - b indegree[b]; } PriorityQueueInteger heap new PriorityQueue(); for (int i 1; i n; i) { if (indegree[i] 0) { heap.offer(i); } } ListInteger order new ArrayList(); while (!heap.isEmpty()) { int u heap.poll(); order.add(u); for (int v : graph[u]) { indegree[v]--; if (indegree[v] 0) { heap.offer(v); } } } if (order.size() n) { System.out.println(-1); } else { StringBuilder sb new StringBuilder(); for (int x : order) { sb.append(x).append( ); } System.out.println(sb.toString().trim()); } } }两个小提醒编号从 1 开始indegree和graph数组都要开n 1别开成n否则最后一个节点越界输出用StringBuilder拼接比循环调用System.out.print快很多。数据量小无所谓数据量大时这个差别能感知到。3.2 C性能优先但有两个反直觉的APIC 版最大的坑是priority_queue默认是大顶堆想要小顶堆必须用greaterint反转比较规则。另外 IO 一定要关同步不然cin读大输入会慢得离谱。#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin n m; vectorvectorint graph(n 1); vectorint indegree(n 1, 0); for (int i 0; i m; i) { int a, b; cin a b; graph[a].push_back(b); indegree[b]; } priority_queueint, vectorint, greaterint pq; for (int i 1; i n; i) { if (indegree[i] 0) { pq.push(i); } } vectorint order; while (!pq.empty()) { int u pq.top(); pq.pop(); order.push_back(u); for (int v : graph[u]) { indegree[v]--; if (indegree[v] 0) { pq.push(v); } } } if ((int)order.size() n) { cout -1 \n; } else { for (int x : order) { cout x ; } cout \n; } return 0; }C 里需要留意的点priority_queueint, vectorint, greaterint是固定写法少一个模板参数都不行order.size()返回的是size_t和n比较时建议强转成int避免无符号比较的警告ios::sync_with_stdio(false); cin.tie(nullptr);这两行建议凡是用了cin/cout的题都加上能大幅提升读取速度。3.3 Python代码最短但要注意IOPython 版本代码量最少核心就是heapq最小堆。读入用sys.stdin.readline不要用input()因为input()内部实现有额外开销OJ 大数据下容易被卡。import sys import heapq def solve(): input sys.stdin.readline n, m map(int, input().split()) graph [[] for _ in range(n 1)] indegree [0] * (n 1) for _ in range(m): a, b map(int, input().split()) graph[a].append(b) indegree[b] 1 heap [] for i in range(1, n 1): if indegree[i] 0: heapq.heappush(heap, i) order [] while heap: u heapq.heappop(heap) order.append(u) for v in graph[u]: indegree[v] - 1 if indegree[v] 0: heapq.heappush(heap, v) if len(order) n: print(-1) else: print(*order) if __name__ __main__: solve()Python 的print(*order)写起来很爽但如果 n 很大比如几万个数字建议改成sys.stdout.write( .join(map(str, order)) \n)避免print一次调用带来的额外开销。另外这个解题函数我习惯包在solve()里而不是直接裸写在全局因为多组数据时更容易做隔离避免变量互相污染。3.4 三份代码放一起时最容易被忽略的差异三种语言的核心逻辑完全一致差别主要在语法和 IO 技巧上。我整理了一张对照表环节JavaCPython最小堆实现PriorityQueueIntegerpriority_queueint, vectorint, greaterintheapq堆顶获取与删除poll()top()pop()heappop()输入优化BufferedReader或Scannerios::sync_with_stdio(false)sys.stdin.readline节点编号偏移数组开n 1数组开n 1列表长度n 1结果拼接StringBuilder循环输出 换行 .join(map(str, order))说实话这道题用任何一种语言都能写几乎不会出现语言本身成为瓶颈的情况。真正让参赛者在考场上翻车的反而是下面这一节要说的输入输出和边界条件。4. 在线测试实战输入输出、边界与多组数据处理4.1 判断当前是单组还是多组数据大多数在线评测系统不管是赛码、牛客还是公司自研的OJ第一行都会给你n和m测一组就退出。但有一部分题会写成“多组测试数据处理到文件末尾”这种情况下如果只按单组写往往只能过样例提交直接 WA。C 处理多组数据的标准姿势是这样的while (cin n m) { graph.assign(n 1, vectorint()); indegree.assign(n 1, 0); // 读入 m 条依赖关系并处理 // 输出当前这组的结果 }同样Java 可以用while (sc.hasNext())Python 可以 try/except 捕获EOFError或者用while True: try: line input() except EOFError: break我见过太多人“本地跑得很好一交就错”原因是本地只测了单组平台给的是多组邻接表和入度数组没清空上一组的数据残留到了下一组。如果你不确定题目是单组还是多组保险起见直接按多组写单组数据也能正常处理。4.2 自测用例怎么造四个必测场景我把这道题的自测用例总结成了四类每一类对应一个容易出错的点场景输入预期输出验证点普通依赖4 3 / 1 2 / 3 2 / 2 41 3 2 4字典序最小的拓扑序链式依赖3 2 / 1 2 / 2 31 2 3完全链不能乱序存在环3 3 / 1 2 / 2 3 / 3 1-1环检测无依赖3 01 2 3全部入度为 0 的情况还有一个细节容易被忽略自环。如果输入里有a b也就是某个业务依赖它自己比如2 2那么节点 2 的入度会变成 1它永远不可能入度为 0。虽然这种输入从业务逻辑上看很奇怪但OJ的数据里出现自环并不罕见代码必须能正确输出 -1。4.3 这几个坑至少让很多人WA一次说几个我在实际刷题和带人时反复遇到的典型错误第一调试输出没删干净。不少人会在代码里加System.out.println(当前处理节点: u);或者cout visiting u endl;来排查问题交上去之前忘了删。在线评测只看标准输出多打任何一行都会被判 WA。第二边建反了。题目说 (a, b) 表示 a 必须在 b 之前结果代码里写成graph[b].add(a)样例没准能过因为某些数据正反都能输出合法序列但字典序要求下就完全不对。我的习惯是先在草稿纸上写清楚“谁指向谁”再敲代码。第三入度减一放在循环外。有同学把indegree[v]--写在遍历后继节点的循环外面这样每个后继节点都少了递减逻辑全乱。记住必须遍历 u 的所有出边对每一条边对应的 v 减一。第四用了while (n--)导致后续 n 被改变。如果读入的是 n 和 m然后 m 条边最好写成for (int i 0; i m; i)而不是while (m--)。后者会改变 m 的原值后面想用 n 或 m 参与计算时就会出问题。4.4 大输入量下的提速模板如果数据规模到了 10 万甚至百万输入优化就不再是“可选”而是“必须”。Java 里Scanner的nextInt()在百万级输入面前会明显吃力建议换成BufferedReader加StringTokenizerBufferedReader br new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st new StringTokenizer(br.readLine()); int n Integer.parseInt(st.nextToken()); int m Integer.parseInt(st.nextToken());C 只要不混用cin和scanf并且关掉同步百万级输入基本没问题。Python 则一定要用sys.stdin.buffer.read()一次性读入再切分这是大数据量下最稳的方案import sys data list(map(int, sys.stdin.buffer.read().split())) n, m data[0], data[1]这种写法把整个输入一次读完比一行一行readline快很多。不过要注意一次性读入后后续取数据要维护一个指针或索引不能再用input()了。5. 面试官想看到的不只是“会背模板”5.1 先答队列版再主动升级成堆版这道题在面试场景下的标准答法绝对不是上来就甩最小堆代码。我更推荐这种方式先给出最容易理解的 Kahn 算法——普通队列O(n m)把依赖关系建模成有向图用入度筛选可执行节点。然后主动补一句“如果题目要求字典序最小的方案可以把普通队列换成优先队列每次弹出编号最小的节点复杂度变成 O(n log n m)。”这种由浅入深的讲述方式比直接背一段完整代码更有说服力因为面试官能看到你理解每一步在解决什么问题。先基础再优化这是一个工程师最顺滑的表达逻辑。5.2 备选方案DFS后序反转加三色标记除了 Kahn 算法拓扑排序还有另一种 DFS 实现。核心思路是深度优先遍历访问完一个节点的所有后继之后再把该节点放入结果列表最后把结果反转得到拓扑序。同时用三个状态标记节点0 表示未访问1 表示访问中2 表示已经完成。如果在遍历过程中碰到状态为 1 的节点说明存在环。Python 伪代码大致是这样state [0] * (n 1) order [] cycle False def dfs(u): global cycle if cycle: return state[u] 1 for v in graph[u]: if state[v] 0: dfs(v) elif state[v] 1: cycle True return state[u] 2 order.append(u) for i in range(1, n 1): if state[i] 0: dfs(i) if cycle: print(-1) else: print(*order[::-1])为什么最后要order[::-1]因为 DFS 中最早被完成的是依赖链最深处的节点它会被先加入order最上层的节点反而最后加入。拓扑序要求父节点在前、子节点在后所以必须反转。这个方法在面试中可以提一嘴说明你理解图的遍历而不只会套模板。它的局限是不容易直接输出字典序最小方案所以如果题目明确要字典序优先选 Kahn 最小堆如果能保证输入是无环的 DAGDFS 后序反转也是一种很优雅的解法。5.3 这道题还能怎么考变体思路面试官很喜欢在这道题的基础上继续追问常见的变体有几种只问“能否完成所有业务”不问具体顺序。这种最简单只需要在 Kahn 结束后检查结果数量是否等于 n等于就输出 1否则输出 -1连结果序列都不用保存。求拓扑序是否唯一。判断方法是 Kahn 执行过程中候选集合是否始终保持最多只有一个节点。如果某一步候选集合里有多个入度为 0 的节点说明当前有几个业务都是“准备好了”的状态先做哪个都合法拓扑序就不唯一。这个变体在很多二面题里出现过。业务带权重求最早完成时间。每个业务有一个执行耗时依赖关系不变要求所有业务完成的最早时间。做法是拓扑排序的过程中同时做 DPdp[v] max(dp[v], dp[u] cost[v])这其实就是关键路径的思路。如果面试聊到这里基本已经超出原题难度不少了。反向依赖。题目如果改成“业务 b 开始之后才能开始 a”那就是反向建图跑法和原题完全一样。关键在于不要被文字绕晕先把“谁依赖谁”写成箭头再决定建图方向。5.4 我个人的三个体会这道题我前后刷了三遍每一遍都有新的发现。第一遍以为就是一个普通拓扑排序用队列秒过结果没看到字典序要求第二遍改成最小堆才发现自己写错了建图方向第三遍才认真处理了多组输入和数组清空的问题。如果读者只能带走三条经验我希望是这三条第一拓扑排序题的核心永远是“入度为 0 的节点就是当前可执行任务”无论是 Kahn 还是 DFS都是围绕这个本质在转。第二字典序要求直接用最小堆没有例外。第三OJ 上让你挂掉的往往不是算法本身而是输入输出、数组越界、多组数据残留这些细节。动手写代码之前花两分钟把输入边界和自测用例想清楚比节省那一两分钟写代码要划算得多。