1from collections import defaultdict, deque
2class Solution:
3 def buildOrder(self, projects, dependencies):
4 res = []
5 if len(projects) == 0: return res
6
7 inEdges = {project: 0 for project in projects}
8 adjList = defaultdict(list)
9
10 for u, v in dependencies:
11 adjList[u].append(v)
12 inEdges[v] += 1
13
14 queue = deque()
15 for node in inEdges:
16 if inEdges[node] == 0:
17 queue.append(node)
18 inEdges[node] -= 1
19
20 while queue:
21 node = queue.popleft()
22 res.append(node)
23 for neighbour in adjList[node]:
24 inEdges[neighbour] -= 1
25 if inEdges[neighbour] == 0: queue.append(neighbour)
26
27 if len(res) != len(projects): return False
28 return res