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

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.

So, basically we have two variables: self.Visited = [0] * numCourses where we keep our colors and 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. Not, that graph is 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 canFinish(self, numCourses, prerequisites):
        self.adj_dict = defaultdict(set)
        for i, j in prerequisites:
            self.adj_dict[i].add(j)

        self.Visited = [0] * numCourses
        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 self.FoundCycle == 0

    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

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