forked from tiationg-kho/leetcode-pattern-500
-
Notifications
You must be signed in to change notification settings - Fork 0
/
1136-parallel-courses.py
32 lines (28 loc) · 937 Bytes
/
1136-parallel-courses.py
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
from collections import deque
class Solution:
def minimumSemesters(self, n: int, relations: List[List[int]]) -> int:
graph = [[] for _ in range(n)]
indegrees = [0 for _ in range(n)]
for p, q in relations:
p -= 1
q -= 1
graph[p].append(q)
indegrees[q] += 1
queue = deque([])
for i, indegree in enumerate(indegrees):
if indegree == 0:
queue.append((i, 1))
res = []
while queue:
node, step = queue.popleft()
res.append(node)
if len(res) == n:
return step
for neighbor in graph[node]:
indegrees[neighbor] -= 1
if indegrees[neighbor] == 0:
queue.append((neighbor, step + 1))
return - 1
# time O(V+E)
# space O(V+E)
# using graph and kahn and topological sort