Leetcode课程表II：存在多解时如何返回课程号升序的拓扑排序结果

核心改造点非常简单：把标准拓扑排序使用的普通队列，替换为*小顶堆（优先队列）*即可，核心逻辑是每次从所有当前无前置依赖的课程中，选择编号最小的课程优先处理，最终就能得到升序优先的合法拓扑排序。

具体实现步骤 #

• 预处理阶段和标准拓扑排序完全一致：统计每门课程的入度，同时构建邻接表存储课程依赖关系（即修完某门课后可以解锁的后续课程列表）
• 初始化小顶堆，将所有入度为0的课程编号加入堆中
• 循环处理堆内元素：
  • 弹出堆顶元素（当前可用的最小课程编号），加入结果数组
  • 遍历该课程的所有后续课程，将对应课程的入度值减1
  • 如果某门后续课程的入度减到0，说明它的所有前置依赖已经修完，将其加入小顶堆
• 最后校验结果数组的长度：如果等于总课程数，直接返回结果数组；否则说明课程依赖存在环，返回空数组

代码示例（Python） #

import heapq
from typing import List

class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        # 构建邻接表和入度数组
        adj = [[] for _ in range(numCourses)]
        in_degree = [0] * numCourses
        for cur, pre in prerequisites:
            adj[pre].append(cur)
            in_degree[cur] += 1
        
        # 小顶堆存放入度为0的课程
        heap = []
        for i in range(numCourses):
            if in_degree[i] == 0:
                heapq.heappush(heap, i)
        
        res = []
        while heap:
            cur = heapq.heappop(heap)
            res.append(cur)
            for next_course in adj[cur]:
                in_degree[next_course] -= 1
                if in_degree[next_course] == 0:
                    heapq.heappush(heap, next_course)
        
        return res if len(res) == numCourses else []

正确性说明 #

我们每次都优先选择当前所有无依赖的课程里编号最小的，全程保证所有能选的课程中，最小的永远被优先安排，最终得到的序列就是所有合法拓扑排序里课程编号升序优先级最高的解。
时间复杂度为O(N log N + E)，其中N是课程总数，E是依赖关系总数，完全可以满足题目数据规模要求。

内容的提问来源于stack exchange，提问作者sam