Medium

题目描述

你总共需要上 numCourses 门课程，课程编号从 0 到 numCourses - 1。给你一个数组 prerequisites，其中 prerequisites[i] = [ai, bi] 表示如果你想选修课程 bi，你必须先选修课程 ai。

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

先修课程也可以是间接的。如果课程 a 是课程 b 的先修课程且课程 b 是课程 c 的先修课程，那么课程 a 就是课程 c 的先修课程。

你还会得到一个查询数组 queries，其中 queries[j] = [uj, vj]。对于第 j 个查询，你应该回答课程 uj 是否是课程 vj 的先修课程。

返回一个布尔数组 answer，其中 answer[j] 是第 j 个查询的答案。

示例 1：

输入：numCourses = 2, prerequisites = [[1,0]], queries = [[0,1],[1,0]]
输出：[false,true]
解释：先修课程对 [1, 0] 表示：想要学习课程 0，你需要先完成课程 1。
课程 0 不是课程 1 的先修课程，但课程 1 是课程 0 的先修课程。

示例 2：

输入：numCourses = 2, prerequisites = [], queries = [[1,0],[0,1]]
输出：[false,false]
解释：没有先修课程对，所以每门课程之间是独立的。

示例 3：

输入：numCourses = 3, prerequisites = [[1,2],[1,0],[2,0]], queries = [[1,0],[1,2]]
输出：[true,true]

约束条件：

  • 2 <= numCourses <= 100
  • 0 <= prerequisites.length <= (numCourses * (numCourses - 1) / 2)
  • prerequisites[i].length == 2
  • 0 <= ai, bi <= numCourses - 1
  • ai != bi
  • 所有先修课程对 [ai, bi] 都是 不同 的
  • 先修课程图中没有环
  • 1 <= queries.length <= 10^4
  • 0 <= ui, vi <= numCourses - 1
  • ui != vi

解题思路

这道题要求我们判断课程之间是否存在间接或直接的先修关系。我们需要找到课程图中的可达性关系。

方法一：Floyd-Warshall算法（推荐） 将课程关系看作有向图，使用Floyd-Warshall算法求出所有节点对之间的可达性。这是一种动态规划方法，时间复杂度为O(n³)，但由于n≤100，完全可行。

方法二：从每个节点BFS/DFS 对每个课程作为起点进行BFS或DFS，找到所有可达的课程。时间复杂度为O(n²+nm)，其中m为边数。

方法三：拓扑排序+DP 使用拓扑排序处理课程依赖关系，同时用动态规划维护可达性关系。

Floyd-Warshall算法最直观且实现简单：

  1. 初始化可达矩阵，直接相邻的课程设为true
  2. 通过中间节点k更新所有节点对(i,j)的可达性
  3. 如果i→k可达且k→j可达，则i→j可达
  4. 最后根据查询直接从矩阵中获取答案

这种方法的优势是预处理后查询时间为O(1)，适合多次查询的场景。

代码实现

class Solution {
public:
    vector<bool> checkIfPrerequisite(int numCourses, vector<vector<int>>& prerequisites, vector<vector<int>>& queries) {
        vector<vector<bool>> isReachable(numCourses, vector<bool>(numCourses, false));
        
        // 初始化直接的先修关系
        for (auto& prereq : prerequisites) {
            isReachable[prereq[0]][prereq[1]] = true;
        }
        
        // Floyd-Warshall算法求传递闭包
        for (int k = 0; k < numCourses; k++) {
            for (int i = 0; i < numCourses; i++) {
                for (int j = 0; j < numCourses; j++) {
                    isReachable[i][j] = isReachable[i][j] || (isReachable[i][k] && isReachable[k][j]);
                }
            }
        }
        
        vector<bool> result;
        for (auto& query : queries) {
            result.push_back(isReachable[query[0]][query[1]]);
        }
        
        return result;
    }
};

class Solution:
    def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:
        isReachable = [[False] * numCourses for _ in range(numCourses)]
        
        # 初始化直接的先修关系
        for prereq in prerequisites:
            isReachable[prereq[0]][prereq[1]] = True
        
        # Floyd-Warshall算法求传递闭包
        for k in range(numCourses):
            for i in range(numCourses):
                for j in range(numCourses):
                    isReachable[i][j] = isReachable[i][j] or (isReachable[i][k] and isReachable[k][j])
        
        result = []
        for query in queries:
            result.append(isReachable[query[0]][query[1]])
        
        return result

public class Solution {
    public IList<bool> CheckIfPrerequisite(int numCourses, int[][] prerequisites, int[][] queries) {
        bool[,] isReachable = new bool[numCourses, numCourses];
        
        // 初始化直接的先修关系
        foreach (var prereq in prerequisites) {
            isReachable[prereq[0], prereq[1]] = true;
        }
        
        // Floyd-Warshall算法求传递闭包
        for (int k = 0; k < numCourses; k++) {
            for (int i = 0; i < numCourses; i++) {
                for (int j = 0; j < numCourses; j++) {
                    isReachable[i, j] = isReachable[i, j] || (isReachable[i, k] && isReachable[k, j]);
                }
            }
        }
        
        List<bool> result = new List<bool>();
        foreach (var query in queries) {
            result.Add(isReachable[query[0], query[1]]);
        }
        
        return result;
    }
}

var checkIfPrerequisite = function(numCourses, prerequisites, queries) {
    const isReachable = Array(numCourses).fill().map(() => Array(numCourses).fill(false));
    
    // 初始化直接的先修关系
    for (const prereq of prerequisites) {
        isReachable[prereq[0]][prereq[1]] = true;
    }
    
    // Floyd-Warshall算法求传递闭包
    for (let k = 0; k < numCourses; k++) {
        for (let i = 0; i < numCourses; i++) {
            for (let j = 0; j < numCourses; j++) {
                isReachable[i][j] = isReachable[i][j] || (isReachable[i][k] && isReachable[k][j]);
            }
        }
    }
    
    const result = [];
    for (const query of queries) {
        result.push(isReachable[query[0]][query[1]]);
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型大小
时间复杂度O(n³ + q)，其中 n 是课程数，q 是查询数。Floyd-Warshall算法需要 O(n³)，处理查询需要 O(q)
空间复杂度O(n²)，用于存储可达性矩阵