Leetcode 210 Course Schedule II Python 3 Solution

Approach - We will first create a graph out of this problem, Every pre-requisite course is connected to the course so the Pre=requisite course will be directing towards the course so we will create a Directed Acyclic Graph. We will find if there is any cycle in the graph and if it is so then taking all the courses will not be possible. To find if there is any cycle in the graph we will use an earlier discussed approach we took in Course Schedule I. We will use Topological Sort to get the order in which we need to take the course so that we take all the pre-requisites before the courses. If you have any doubt just let me know in the comments.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44


class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        
        white = set()
        black = set()
        grey  = set()
        top_sort = []
        # visited = set()
        connections = dict()
        for p in prerequisites:
            if p[1] not in connections:
                connections[p[1]] = set()
            connections[p[1]].add(p[0])
        for i in range(numCourses):
            white.add(i)
            # white.add(p[0])
            
        def traverse(root):
            if root in grey:
                #we have found cycle in our graph
                return False
            grey.add(root)
            
            if root in connections:
                for node in connections[root]:
                    if node not in black:
                        ans = traverse(node)
                        if not ans:
                            return False
            
            grey.remove(root)
            if root not in black:
                top_sort.append(root)
            black.add(root)
            
            return True
        
        for w in white:
            ans = traverse(w)
            if not ans:
                top_sort = []
                break
        return top_sort[::-1]
        