class Solution:

    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:

        indegree = [0 for _ in range(numCourses)]

        adj = [[] for _ in range(numCourses)]

        for cur,pre in prerequisites:

            adj[pre].append(cur)

            indegree[cur] += 1

        res = []

        queue = []

        for i in range(numCourses):

            if indegree[i] == 0:

                queue.append(i)

        while queue:

            i = queue.pop(0)

            res.append(i)

            for j in adj[i]:

                indegree[j] -= 1

                if indegree[j] == 0:

                    queue.append(j)

        return res if len(res) == numCourses else []

class Solution:

    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:

        def dfs(i, adjacency, flags):

            if flags[i] == -1: return True

            if flags[i] == 1: return False

            flags[i] = 1

            for j in adjacency[i]:

                if not dfs(j, adjacency, flags): return False

            flags[i] = -1

            res.append(i)

            return True

        res = []

        adjacency = [[] for _ in range(numCourses)]

        flags = [0 for _ in range(numCourses)]

        for cur, pre in prerequisites:

            adjacency[pre].append(cur)

        for i in range(numCourses):

            if not dfs(i, adjacency, flags): return []

        return res[::-1]