-
Notifications
You must be signed in to change notification settings - Fork 0
/
Course Schedule IV
29 lines (26 loc) · 966 Bytes
/
Course Schedule IV
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
class Solution:
def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:
seen = [0]* numCourses
path={idx: set() for idx in range(numCourses)}
incoming = [0]* numCourses
answer= []
graph={idx: [] for idx in range(numCourses)}
for fro_m , to in prerequisites:
incoming[to]+=1
graph[fro_m].append(to)
queue = deque()
for idx in range(numCourses):
if incoming[idx] == 0:
queue.append(idx)
while queue:
node = queue.popleft()
for adj in graph[node]:
path[adj].add(node)
path[adj].update(path[node])
incoming[adj] -= 1
if incoming[adj] == 0:
queue.append(adj)
answer= []
for u,v in queries:
answer.append(u in path[v])
return answer