【LetMeFly】1462.课程表 IV:拓扑排序
力扣题目链接:https://leetcode.cn/problems/course-schedule-iv/
你总共需要上 numCourses
门课,课程编号依次为 0
到 numCourses-1
。你会得到一个数组 prerequisite
,其中 prerequisites[i] = [ai, bi]
表示如果你想选 bi
课程,你 必须 先选 ai
课程。
- 有的课会有直接的先修课程,比如如果想上课程
1
,你必须先上课程 0
,那么会以 [0,1]
数对的形式给出先修课程数对。
先决条件也可以是 间接 的。如果课程 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]
解释:课程 0 不是课程 1 的先修课程,但课程 1 是课程 0 的先修课程。
TEXT
示例 2:
输入:numCourses = 2, prerequisites = [], queries = [[1,0],[0,1]]
输出:[false,false]
解释:没有先修课程对,所以每门课程之间是独立的。
TEXT
示例 3:

输入:numCourses = 3, prerequisites = [[1,2],[1,0],[2,0]], queries = [[1,0],[1,2]]
输出:[true,true]
TEXT
提示:
2 <= numCourses <= 100
0 <= prerequisites.length <= (numCourses * (numCourses - 1) / 2)
prerequisites[i].length == 2
0 <= ai, bi <= n - 1
ai != bi
- 每一对
[ai, bi]
都 不同
- 先修课程图中没有环。
0 <= ui, vi <= n - 1
ui != vi
方法一:拓扑排序
首先,在确定课程的先后关系上,这道题类似于LeetCode 207.课程表,使用拓扑排序进行解决即可。
那么,问题是对于个query,如何快速返回每次的查询呢?
我们可以建立一个的布尔类型的数组。代表课程是否为课程的先修课。(这样,对于某个查询,只需要返回即可)
在拓扑排序时,如果确定了thisCourse是nextCourse的先修课,那么所有thisCourse的先修课都是nextCourse的先修课。用公式表示即为:
- 时间复杂度,其中是先修课关系数,是查询的个数
- 空间复杂度
AC代码
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44
| class Solution { public: vector<bool> checkIfPrerequisite(int numCourses, vector<vector<int>>& prerequisites, vector<vector<int>>& queries) { vector<vector<int>> graph(numCourses); vector<int> indegree(numCourses); for (vector<int>& ab : prerequisites) { graph[ab[0]].push_back(ab[1]); indegree[ab[1]]++; }
queue<int> q; for (int i = 0; i < numCourses; i++) { if (!indegree[i]) { q.push(i); } }
vector<vector<bool>> isPre(numCourses, vector<bool>(numCourses, false)); while (q.size()) { int thisCourse = q.front(); q.pop(); for (int nextCourse : graph[thisCourse]) { indegree[nextCourse]--; if (!indegree[nextCourse]) { q.push(nextCourse); } isPre[thisCourse][nextCourse] = true; for (int i = 0; i < numCourses; i++) { isPre[i][nextCourse] = isPre[i][nextCourse] | isPre[i][thisCourse]; } } }
vector<bool> ans; for (vector<int>& q : queries) { ans.push_back(isPre[q[0]][q[1]]); } return ans; } };
CPP
|
今日才发现vector没有|=、+= ….
Python
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
|
class Solution: def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]: graph = [[] for _ in range(numCourses)] indegree = [0] * numCourses for a, b in prerequisites: graph[a].append(b) indegree[b] += 1 q = [] for i in range(numCourses): if not indegree[i]: q.append(i) isPre = [[False for _ in range(numCourses)] for __ in range(numCourses)] while q: thisCourse = q.pop() for nextCourse in graph[thisCourse]: indegree[nextCourse] -= 1 if not indegree[nextCourse]: q.append(nextCourse) isPre[thisCourse][nextCourse] = True for i in range(numCourses): isPre[i][nextCourse] |= isPre[i][thisCourse] ans = [] for a, b in queries: ans.append(isPre[a][b]) return ans
PYTHON
|
同步发文于CSDN,原创不易,转载经作者同意后请附上原文链接哦~
Tisfy:https://letmefly.blog.csdn.net/article/details/132825649