Medium

题目描述

你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1。

在选修某些课程之前需要一些先修课程。先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi。

  • 例如，先修课程对 [0, 1] 表示：想要学习课程 0，你需要先完成课程 1。

请你判断是否可能完成所有课程的学习？如果可以，返回 true；否则，返回 false。

示例 1：

输入：numCourses = 2, prerequisites = [[1,0]]
输出：true
解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的。

示例 2：

输入：numCourses = 2, prerequisites = [[1,0],[0,1]]
输出：false
解释：总共有 2 门课程。学习课程 1 之前，你需要先完成课程 0；并且学习课程 0 之前，你还应先完成课程 1。这是不可能的。

提示：

  • 1 <= numCourses <= 2000
  • 0 <= prerequisites.length <= 5000
  • prerequisites[i].length == 2
  • 0 <= ai, bi < numCourses
  • prerequisites[i] 中的所有课程对 互不相同

解题思路

这道题本质上是判断有向图中是否存在环。如果存在环，说明课程之间存在循环依赖，无法完成所有课程；如果不存在环，则可以完成。

主要有两种解法：

方法一：拓扑排序（推荐）

  • 构建邻接表和入度数组
  • 将所有入度为0的节点加入队列
  • 不断取出入度为0的节点，将其邻接节点的入度减1
  • 如果某个邻接节点入度变为0，则加入队列
  • 最终判断处理过的节点数是否等于总课程数

方法二：DFS检测环

  • 使用三种状态：未访问(0)、访问中(1)、已完成(2)
  • 对每个未访问的节点进行DFS
  • 如果在DFS过程中遇到访问中的节点，说明存在环
  • 访问完成后将节点标记为已完成

拓扑排序相对更直观，也是处理课程依赖问题的经典方法。

代码实现

class Solution {
public:
    bool canFinish(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;
        for (int i = 0; i < numCourses; i++) {
            if (indegree[i] == 0) {
                q.push(i);
            }
        }
        
        int count = 0;
        while (!q.empty()) {
            int course = q.front();
            q.pop();
            count++;
            
            for (int next : graph[course]) {
                indegree[next]--;
                if (indegree[next] == 0) {
                    q.push(next);
                }
            }
        }
        
        return count == numCourses;
    }
};

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        graph = [[] for _ in range(numCourses)]
        indegree = [0] * numCourses
        
        for ai, bi in prerequisites:
            graph[bi].append(ai)
            indegree[ai] += 1
        
        queue = []
        for i in range(numCourses):
            if indegree[i] == 0:
                queue.append(i)
        
        count = 0
        while queue:
            course = queue.pop(0)
            count += 1
            
            for next_course in graph[course]:
                indegree[next_course] -= 1
                if indegree[next_course] == 0:
                    queue.append(next_course)
        
        return count == numCourses

public class Solution {
    public bool CanFinish(int numCourses, int[][] prerequisites) {
        var graph = new List<int>[numCourses];
        var 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]]++;
        }
        
        var queue = new Queue<int>();
        for (int i = 0; i < numCourses; i++) {
            if (indegree[i] == 0) {
                queue.Enqueue(i);
            }
        }
        
        int count = 0;
        while (queue.Count > 0) {
            int course = queue.Dequeue();
            count++;
            
            foreach (int next in graph[course]) {
                indegree[next]--;
                if (indegree[next] == 0) {
                    queue.Enqueue(next);
                }
            }
        }
        
        return count == numCourses;
    }
}

var canFinish = function(numCourses, prerequisites) {
    const graph = Array.from({ length: numCourses }, () => []);
    const indegree = Array(numCourses).fill(0);
    
    for (const [ai, bi] of prerequisites) {
        graph[bi].push(ai);
        indegree[ai]++;
    }
    
    const queue = [];
    for (let i = 0; i < numCourses; i++) {
        if (indegree[i]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型拓扑排序
时间复杂度O(V + E)
空间复杂度O(V + E)

其中 V 是课程数量（节点数），E 是先修课程关系数量（边数）。

相关题目