Course Schedule II

course_schedule_ii.py

class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        marked = set()
        order = []
        g = {}
        cycle = False
        onStack = [False for _ in range(numCourses)]

        for v in range(numCourses):
            g[v] = set()
        for (u,v) in prerequisites:
            g[u].add(v)

        def dfs(v, visited):
            nonlocal cycle
            nonlocal onStack
            visited.add(v)
            onStack[v] = True
            for u in g[v]:
                if cycle:
                    return
                elif u not in visited:
                    dfs(u, visited)
                elif onStack[u]:
                    cycle = True
                    return
            
            onStack[v] = False
            order.append(v)
        
        for k in list(g):
            if k not in marked:
                dfs(k, marked)
        
        if cycle:
            return []
        
        return order