课程排序问题：寻求正确且最优的拓扑排序解决方案

Hey there! 你的问题本质上是经典的拓扑排序问题，这类问题最适合用Kahn算法（基于入度表的BFS）或者DFS递归标记法来解决，这两种方法都能高效检测循环依赖，并且性能远优于你当前的实现。

先给你直接上最优解，再逐部分拆解说明：

方案一：Kahn算法（BFS实现，推荐） #

Kahn算法通过维护每个节点的入度（即需要完成的先修课数量），每次选择入度为0的节点加入结果，然后更新其后续节点的入度，直到所有节点处理完毕或者发现有节点始终无法入度为0（循环依赖）。

适配课程编号1~N的代码 #

from collections import deque

class Solution:
    def findOrder(self, numCourses: int, prerequisites: list[list[int]]) -> list[int]:
        # 构建邻接表和入度表，适配课程编号1~numCourses
        adjacency = [[] for _ in range(numCourses + 1)]  # 索引0闲置，1~numCourses对应课程
        in_degree = [0] * (numCourses + 1)
        
        for course, prereq in prerequisites:
            # 先修课prereq完成后才能修course，建立prereq到course的指向
            adjacency[prereq].append(course)
            in_degree[course] += 1
        
        # 初始化队列，加入所有无先修课的课程（入度为0）
        queue = deque()
        for i in range(1, numCourses + 1):
            if in_degree[i] == 0:
                queue.append(i)
        
        # 执行BFS遍历
        result = []
        while queue:
            current_course = queue.popleft()
            result.append(current_course)
            # 更新当前课程所有后续课程的入度
            for next_course in adjacency[current_course]:
                in_degree[next_course] -= 1
                # 如果后续课程的先修课已全部完成，加入队列
                if in_degree[next_course] == 0:
                    queue.append(next_course)
        
        # 检查是否所有课程都被处理：若结果长度不等于课程数，说明存在循环依赖
        return result if len(result) == numCourses else []

代码细节说明 #

• 数据结构：邻接表存储课程的后续依赖，入度表记录每个课程需要的先修课数量，空间复杂度为O(n+m)（n是课程数，m是先修关系数）；
• 时间效率：O(n+m)，每个课程和先修关系仅被处理一次，性能拉满；
• 循环检测：若最终结果长度小于课程数，说明有课程始终无法满足先修条件，存在循环依赖，直接返回空列表；
• 示例验证：
  • 输入示例1：numCourses=4, prerequisites=[[1,2],[3,2],[2,4]]，输出会是[1,3,2,4]或[3,1,2,4]（队列顺序不影响合法性）；
  • 输入示例2：numCourses=2, prerequisites=[[1,2],[2,1]]，输出为[]，完全符合要求。

方案二：DFS递归标记法 #

另一种思路是通过DFS遍历每个节点，标记节点的状态（未访问、访问中、已访问），如果在遍历过程中遇到状态为「访问中」的节点，说明存在循环依赖。

class Solution:
    def findOrder(self, numCourses: int, prerequisites: list[list[int]]) -> list[int]:
        # 构建邻接表，适配课程编号1~numCourses
        adjacency = [[] for _ in range(numCourses + 1)]
        for course, prereq in prerequisites:
            adjacency[prereq].append(course)
        
        # 状态标记：0=未访问，1=访问中（当前递归栈中），2=已访问
        state = [0] * (numCourses + 1)
        result = []
        has_cycle = False
        
        def dfs(node):
            nonlocal has_cycle
            if has_cycle:
                return
            state[node] = 1  # 标记为正在访问
            # 遍历当前课程的所有后续课程
            for neighbor in adjacency[node]:
                if state[neighbor] == 0:
                    dfs(neighbor)
                elif state[neighbor] == 1:
                    # 遇到正在访问的节点，说明存在循环依赖
                    has_cycle = True
                    return
            state[node] = 2  # 标记为已访问完成
            result.append(node)
        
        # 遍历所有未访问的课程
        for i in range(1, numCourses + 1):
            if state[i] == 0 and not has_cycle:
                dfs(i)
        
        # DFS是后序遍历，需要反转结果得到正确的选课顺序；有循环则返回空
        return [] if has_cycle else result[::-1]

代码细节说明 #

• 状态管理：通过三个状态避免重复遍历，同时精准检测循环；
• 时间空间复杂度：同样为O(n+m)，递归栈的深度最坏为O(n)（适合课程数不极端的场景）；
• 结果处理：DFS是先处理完所有先修课再记录当前课程，所以需要反转结果才能得到正确的选课顺序。

对比你的原有代码问题 #

你的代码主要存在以下不足：

1. 无状态追踪：无法记录递归过程中节点的访问状态，因此检测不到循环依赖；
2. 数据结构低效：用字典存储先修关系，递归中频繁修改字典、查找元素，导致时间复杂度极高；
3. 逻辑混乱：递归函数中存在变量引用错误（比如self.mapping[k].remove(value)中的k是循环变量，并非当前需要处理的键），导致逻辑不可靠。

上面两种方案都完美解决了这些问题，其中Kahn算法的迭代实现更直观，也不会出现递归栈溢出的问题（适合大规模课程场景），DFS方法则代码更简洁。

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