210. Course Schedule II

class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        """
        tc O(V+E) sc O(V+E)
        main idea: BFS topological sort
        """
        g = [[] for i in range(numCourses)]
        ingree = [0] * numCourses
        q = collections.deque()
        res = []
        for snd,fst in prerequisites:
            g[fst].append(snd)
            ingree[snd] += 1
        for i in range(numCourses):
            if ingree[i] == 0:
                q.append(i)
        while q:
            cur = q.popleft()
            res.append(cur)
            for child in g[cur]:
                ingree[child] -= 1
                if ingree[child] == 0:
                    q.append(child)
        return res if len(res) == numCourses else []