Leetcode/050_findOrder.py at master · TheSarang/Leetcode · GitHub

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
33
34
35
36
37
38
39
from queue import Queue
class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        adjList = dict()
        inDegree = dict()
        visited = []
        q = Queue()
        for nodes in prerequisites:
            if not nodes[1] in adjList:
                adjList[nodes[1]] = [nodes[0]]
            else:
                adjList[nodes[1]].append(nodes[0])

            if not nodes[0] in inDegree:
                inDegree[nodes[0]] = 1
            else:
                inDegree[nodes[0]] += 1
        print("adjList ", adjList)
        print("inDegree ", inDegree)

        for i in range(numCourses):
            if not i in inDegree:
                q.put(i)

        while not q.empty():
            cur = q.get()
            if cur in adjList:
                for nodes in adjList[cur]:
                    if nodes in inDegree:
                        temp = inDegree[nodes]
                        temp -= 1
                        inDegree[nodes] = temp
                        if inDegree[nodes] == 0:
                            q.put(nodes)
            visited.append(cur)

        if len(visited) != numCourses:
            return []
        return visited