Learning On the Way

210. Course Schedule II

There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai.

For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1. Return the ordering of courses you should take to finish all courses. If there are many valid answers, return any of them. If it is impossible to finish all courses, return an empty array.

from collections import defaultdict 
class Solution: 
    WHITE = 1 
    GRAY = 2 
    BLACK = 3 
    def findOrder(self, numCourses, prerequisites): 
        # Create the adjacency list representation of the graph 
        adj_list = defaultdict(list) 
        # A pair [a, b] in the input represents edge from b --> a 
        for dest, src in prerequisites: 
            adj_list[src].append(dest) 
        topological_sorted_order = [] 
        is_possible = True 
        # By default all vertces are WHITE 
        color = {k: Solution.WHITE for k in range(numCourses)} 
        def dfs(node): 
            nonlocal is_possible 
            # Don't recurse further if we found a cycle already 
            if not is_possible: 
                return 
            # Start the recursion 
            color[node] = Solution.GRAY 
            # Traverse on neighboring vertices 
            if node in adj_list: 
                for neighbor in adj_list[node]: 
                    if color[neighbor] == Solution.WHITE: 
                        dfs(neighbor) 
                    elif color[neighbor] == Solution.GRAY: 
                         # An edge to a GRAY vertex represents a cycle 
                        is_possible = False 
            # Recursion ends. We mark it as black 
            color[node] = Solution.BLACK 
            topological_sorted_order.append(node) 
        for vertex in range(numCourses): 
            # If the node is unprocessed, then call dfs on it. 
            if color[vertex] == Solution.WHITE: 
                dfs(vertex) 
        return topological_sorted_order[::-1] if is_possible else []