Medium

题目描述

现在你总共有 numCourses 门课需要选，记为 0 到 numCourses - 1。给你一个数组 prerequisites ，其中 prerequisites[i] = [ai, bi] ，表示在选修课程 ai 前 必须 先选修 bi 。

  • 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示：[0,1] 。

返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序，你只要返回 任意一种 就可以了。如果不可能完成所有课程，返回 一个空数组 。

示例 1：

输入：numCourses = 2, prerequisites = [[1,0]]
输出：[0,1]
解释：总共有 2 门课程。要学习课程 1，你需要先完成课程 0。因此，正确的课程顺序为 [0,1] 。

示例 2：

输入：numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
输出：[0,2,1,3]
解释：总共有 4 门课程。要学习课程 3，你应该先完成课程 1 和课程 2。并且课程 1 和课程 2 都应该排在课程 0 之后。
因此，一个正确的课程顺序是 [0,1,2,3] 。另一个正确的排序是 [0,2,1,3] 。

示例 3：

输入：numCourses = 1, prerequisites = []
输出：[0]

提示：

  • 1 <= numCourses <= 2000
  • 0 <= prerequisites.length <= numCourses * (numCourses - 1)
  • prerequisites[i].length == 2
  • 0 <= ai, bi < numCourses
  • ai != bi
  • 所有[ai, bi] 互不相同

解题思路

这是一个经典的拓扑排序问题。题目要求找到一个课程的学习顺序，使得所有的先修课程都在后续课程之前。

解题思路：

问题本质是在有向图中找到拓扑排序序列。如果图中存在环，则无法完成所有课程学习。

方法一：BFS + 入度统计（推荐）

  1. 构建邻接表表示有向图，统计每个节点的入度
  2. 将所有入度为0的节点加入队列（这些是可以直接学习的课程）
  3. 每次从队列中取出一个节点，将其加入结果序列
  4. 遍历该节点的所有邻接节点，将它们的入度减1
  5. 如果某个邻接节点入度变为0，将其加入队列
  6. 重复步骤3-5，直到队列为空
  7. 如果结果序列长度等于课程数，说明存在有效的拓扑排序；否则存在环

方法二：DFS + 三色标记 使用白色（0）、灰色（1）、黑色（2）分别表示未访问、正在访问、已访问完成的状态。通过DFS检测环并构建拓扑序列。

时间复杂度：O(V+E)，空间复杂度：O(V+E)，其中V是课程数，E是先修关系数。

代码实现

class Solution {
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>> graph(numCourses);
        vector<int> indegree(numCourses, 0);
        
        // 构建图和计算入度
        for (auto& pre : prerequisites) {
            graph[pre[1]].push_back(pre[0]);
            indegree[pre[0]]++;
        }
        
        queue<int> q;
        vector<int> result;
        
        // 将入度为0的节点加入队列
        for (int i = 0; i < numCourses; i++) {
            if (indegree[i] == 0) {
                q.push(i);
            }
        }
        
        while (!q.empty()) {
            int course = q.front();
            q.pop();
            result.push_back(course);
            
            // 减少邻接节点的入度
            for (int next : graph[course]) {
                indegree[next]--;
                if (indegree[next] == 0) {
                    q.push(next);
                }
            }
        }
        
        return result.size() == numCourses ? result : vector<int>();
    }
};

class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        from collections import deque, defaultdict
        
        graph = defaultdict(list)
        indegree = [0] * numCourses
        
        # 构建图和计算入度
        for course, pre in prerequisites:
            graph[pre].append(course)
            indegree[course] += 1
        
        queue = deque()
        result = []
        
        # 将入度为0的节点加入队列
        for i in range(numCourses):
            if indegree[i] == 0:
                queue.append(i)
        
        while queue:
            course = queue.popleft()
            result.append(course)
            
            # 减少邻接节点的入度
            for next_course in graph[course]:
                indegree[next_course] -= 1
                if indegree[next_course] == 0:
                    queue.append(next_course)
        
        return result if len(result) == numCourses else []

public class Solution {
    public int[] FindOrder(int numCourses, int[][] prerequisites) {
        List<int>[] graph = new List<int>[numCourses];
        int[] indegree = new int[numCourses];
        
        // 初始化图
        for (int i = 0; i < numCourses; i++) {
            graph[i] = new List<int>();
        }
        
        // 构建图和计算入度
        foreach (var pre in prerequisites) {
            graph[pre[1]].Add(pre[0]);
            indegree[pre[0]]++;
        }
        
        Queue<int> queue = new Queue<int>();
        List<int> result = new List<int>();
        
        // 将入度为0的节点加入队列
        for (int i = 0; i < numCourses; i++) {
            if (indegree[i] == 0) {
                queue.Enqueue(i);
            }
        }
        
        while (queue.Count > 0) {
            int course = queue.Dequeue();
            result.Add(course);
            
            // 减少邻接节点的入度
            foreach (int next in graph[course]) {
                indegree[next]--;
                if (indegree[next] == 0) {
                    queue.Enqueue(next);
                }
            }
        }
        
        return result.Count == numCourses ? result.ToArray() : new int[0];
    }
}

var findOrder = function(numCourses, prerequisites) {
    const graph = Array(numCourses).fill(null).map(() => []);
    const indegree = Array(numCourses).fill(0);
    
    // 构建图和计算入度
    for (const [course, pre] of prerequisites) {
        graph[pre].push(course);
        indegree[course]++;
    }
    
    const queue = [];
    const result = [];
    
    // 将入度为0的节点加入队列
    for (let i = 0; i < numCourses; i++) {
        if (indegree[i]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(V + E)V是课程数量，E是先修关系数量。需要遍历所有节点和边
空间复杂度O(V + E)邻接表存储图需要O(V + E)空间，队列和结果数组需要O(V)空间

相关题目