Description
There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course ai first if you want to take course bi.
For example, the pair [0, 1] indicates that you have to take course 0 before you can take course 1.
Prerequisites can also be indirect. If course a is a prerequisite of course b, and course b is a prerequisite of course c, then course a is a prerequisite of course c.
You are also given an array queries where queries[j] = [uj, vj]. For the jth query, you should answer whether course uj is a prerequisite of course vj or not.
Return a boolean array answer, where answer[j] is the answer to the jth query.
Example 1:
Input: numCourses = 2, prerequisites = [[1,0]], queries = [[0,1],[1,0]]
Output: [false,true]
Explanation: The pair [1, 0] indicates that you have to take course 1 before you can take course 0.
Course 0 is not a prerequisite of course 1, but the opposite is true.
Example 2:
Input: numCourses = 2, prerequisites = [], queries = [[1,0],[0,1]]
Output: [false,false]
Explanation: There are no prerequisites, and each course is independent.
Example 3:
Input: numCourses = 3, prerequisites = [[1,2],[1,0],[2,0]], queries = [[1,0],[1,2]]
Output: [true,true]
Constraints:
2 <= numCourses <= 100
0 <= prerequisites.length <= (numCourses * (numCourses - 1) / 2)
prerequisites[i].length == 2
0 <= ai, bi <= n - 1
ai != bi
All the pairs [ai, bi] are unique.
The prerequisites graph has no cycles.
1 <= queries.length <= 104
0 <= ui, vi <= n - 1
ui != vi
Solution
Iterate through all nodes, and keep track of every node’s next nodes, use stack to iterate all possible next nodes.文章来源：https://www.toymoban.com/news/detail-430377.html
Time complexity:
o
(
V
∗
E
)
=
o
(
n
∗
n
2
)
o(V*E)=o(n*n^2)
o(V∗E)=o(n∗n2)
Space complexity:
o
(
V
∗
E
)
=
o
(
n
∗
n
2
)
o(V*E)=o(n*n^2)
o(V∗E)=o(n∗n2)文章来源地址https://www.toymoban.com/news/detail-430377.html
Code
class Solution:
def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:
def build_graph(edges: list) -> dict:
"""
Returns:
{node: [next_node1, next_node2, ...]}
"""
graph = {}
for begin_course, next_course in edges:
if begin_course not in graph:
graph[begin_course] = []
graph[begin_course].append(next_course)
return graph
graph = build_graph(prerequisites)
all_courses = {i: [] for i in range(numCourses)}
for i in range(numCourses):
# need to use deepcopy, otherwise will change graph if stack.pop()
stack = copy.deepcopy(graph.get(i, []))
while stack:
next_course = stack.pop()
if next_course in all_courses[i]:
continue
all_courses[i].append(next_course)
stack += graph.get(next_course, [])
res = []
for u, v in queries:
if v in all_courses[u]:
res.append(True)
else:
res.append(False)
return res
到了这里，关于leetcode-1462. Course Schedule IV的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
