Course schedule IV
September 5, 2022
graphProblem URL: Course schedule IV
We will first create an adjacency list from the prerequisites. Then for each queires, we will start DFS from course 1 to course 2, if we can reach to course 2, then we append true in our result, else we append false. Finally, we will return our result after every queires has been run through.
class Solution:
def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:
self.graph = self.buildGraph(numCourses, prerequisites)
return [self.dfs(c1, c2, set()) for c1, c2 in queries]
def dfs(self, start: int, target: int, visited: set):
if start == target:
return True
visited.add(start)
for neighbor in self.graph[start]:
if neighbor not in visited:
if self.dfs(neighbor, target, visited):
return True
return False
def buildGraph(self, numCourses: int, prerequisites: List[List[int]]) -> dict:
graph = {}
for i in range(numCourses):
graph[i] = []
for c1, c2 in prerequisites:
graph[c1].append(c2)
return graph
Time Complexity: O(q*(n+p))
, q is the number of queires, n is number of courses and p is the number of prerequisites.
Space Complexity: O(n+p)