Course Schedule II LeetCode solution in Python

1
class Solution:
2
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
3
        d = {i: [] for i in range(numCourses)}
4

5
        for crs, prereq in prerequisites:
6
            d[crs].append(prereq)
7

8
        visit, cycle = set(), set()
9
        output = []
10

11
        def dfs(crs):
12
            if crs in cycle:
13
                return False
14
            if crs in visit:
15
                return True
16

17
            cycle.add(crs)
18
            for nei in d[crs]:
19
                if not dfs(nei):
20
                    return False
21
            cycle.remove(crs)
22
            visit.add(crs)
23
            output.append(crs)
24
            return True
25

26
        for crs in range(numCourses):
27
            if not dfs(crs):
28
                return []
29
        return output