https://leetcode.com/problems/course-schedule-ii

This is the classical problem about topological sort: (for more details you can look https://en.wikipedia.org/wiki/Topological_sorting). The basic idea of topological for directed graphs is to check if there cycle in this graph. For example if you have in your schedule dependencies like 0 -> 5, 5-> 3 and 3 -> 0, then we say, that cycle exists and in this case we need to return False.

There are different ways to do topological sort, I prefer to use dfs. The idea is to use classical dfs traversal, but color our nodes into 3 different colors, 0 (white) for node which is not visited yet, 1 (gray) for node which is in process of visiting (not all its neibours are processed), and 2 (black) for node which is fully visited (all its neibours are already processed). The proof can be found for example in classical Cormen book (note, that here we have slightly different notation with inversed edges, so we do not need to reverse list in the end).

So, basically we have three variables: self.Visited = [0] * numCourses where we keep our colors, define self.FoundCycle = 0, we keep it for early stopping, if we found cycle we do not need to continue and we can iterrurupt earlier and Ans is the list we need to return of fully visited nodes. Note, that graph can be not necessarily connected, so we need to start our dfs from all nodes.

Comlexity. We use classical dfs, so time comlexity is O(E+V), where E is number of edges and V is number of vertices. Space complexity is also O(E+V) because we work with adjacency lists.

class Solution:
    def findOrder(self, numCourses, prerequisites):
        self.adj_dict = defaultdict(set)
        for i, j in prerequisites:
            self.adj_dict[i].add(j)

        self.Visited = [0] * numCourses
        self.Ans, self.FoundCycle = [], 0
        
        for i in range(numCourses):
            if self.FoundCycle == 1: break      # early stop if the loop is found
            if self.Visited[i] == 0:
                self.dfs(i)
     
        return [] if self.FoundCycle == 1 else self.Ans

    def dfs(self, start):
        if self.FoundCycle == 1:   return     # early stop if the loop is found    
        if self.Visited[start] == 1:
            self.FoundCycle = 1               # loop is found
        if self.Visited[start] == 0:           # node is not visited yet, visit it
            self.Visited[start] = 1             # color current node as gray
            for neib in self.adj_dict[start]:   # visit all its neibours
                self.dfs(neib)
            self.Visited[start] = 2             # color current node as black
            self.Ans.append(start)              # add node to answer

If you like the solution, you can upvote it on leetcode discussion section: Problem 0210