leetcode-solution/Python/0210-course-schedule-ii.py at main · hogan-tech/leetcode-solution · 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
40
41
42
43
44
45
46
47
48
49
# time complexity: O(V+E)
# space complexity: O(V+E)
from collections import deque
from typing import List


class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        indegree = [0] * numCourses
        adjList = [[] for _ in range(numCourses)]

        for inNode, outNode in prerequisites:
            adjList[outNode].append(inNode)
            indegree[inNode] += 1

        queue = deque()
        for i in range(numCourses):
            if indegree[i] == 0:
                queue.append(i)

        result = []
        count = 0
        while queue:
            node = queue.popleft()
            result.append(node)
            count += 1
            for neighbor in adjList[node]:
                indegree[neighbor] -= 1
                if indegree[neighbor] == 0:
                    queue.append(neighbor)

        if count != numCourses:
            return []

        return result


numCourses = 2
prerequisites = [[1, 0]]
print(Solution().findOrder(numCourses, prerequisites))
numCourses = 4
prerequisites = [[1, 0], [2, 0], [3, 1], [3, 2]]
print(Solution().findOrder(numCourses, prerequisites))
numCourses = 1
prerequisites = []
print(Solution().findOrder(numCourses, prerequisites))
numCourses = 6
prerequisites = [[0, 1], [1, 2], [2, 3], [4, 5], [5, 1], [5, 2]]
print(Solution().findOrder(numCourses, prerequisites))