# memoization using array
class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:

        # DP with memoization
        # state: 0 - unvisited
        # state: 1 - visited but not finished
        # state: 2 - visited and finished
        visit = [0]*numCourses
        from collections import defaultdict
        mapping = defaultdict(list)
        for (crs, prereq) in prerequisites:
            mapping[crs].append(prereq)

        result = []

        def dfs(course):
            if visit[course] == 1:
                return False

            if visit[course] == 2:
                return True

            visit[course] = 1

            for neighbour in mapping[course]:
                run = dfs(neighbour)
                if run is False:
                    return False

            visit[course] = 2
            result.append(course)
            return True

        for crs in range(numCourses):
            run = dfs(crs)
            if run is False:
                return []

        return result

# memoization using set
class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:

        prereq_map = collections.defaultdict(list)
        for crs, prereq in prerequisites:
            prereq_map[crs].append(prereq)

        output = []
        visit, cycle = set(), set()

        # visit counter takes care of whether a node has been added to output
        # cycle counter takes care of whether a node is already part of the "current" cycle
        # once you are at ending point of a possible cycle, you return
        def dfs(crs):
            if crs in cycle:
                return False
            if crs in visit:
                return True
            cycle.add(crs)
            for pre in prereq_map[crs]:
                if dfs(pre) == False:
                    return False
            cycle.remove(crs)
            visit.add(crs)
            output.append(crs)
            return True

        for c in range(numCourses):
            if dfs(c) == False:
                return []

        return output