Clean, easy to understand Python solution based on topological sort (bfs)


  • 0
    A
    import Queue
    
    class Solution(object):
        def findOrder(self, numCourses, prerequisites):
            """
            :type numCourses: int
            :type prerequisites: List[List[int]]
            :rtype: List[int]
            """
            graph = [[] for _ in range(numCourses)]
            visit = [0 for _ in range(numCourses)]
            for x, y in prerequisites:
                graph[y].append(x)
                
            queue = Queue.Queue()
            indegree_map = {}
    
            for i in range(len(graph)):
                indegree_map[i] = self.get_indegree(graph, i)
                # O indegree, no dependency
                if indegree_map[i] == 0:
                    queue.put(i)
    
            sorted_list = []
    
            while not queue.empty():
                vertex = queue.get()
                sorted_list.append(vertex)
    
                for v in graph[vertex]:
                    indegree_map[v] -= 1
                    if indegree_map[v] == 0:
                        queue.put(v)
    
            if len(sorted_list) != numCourses:
                return []
    
            return sorted_list
            
        def get_indegree(self, graph, v):
            indegree = 0
            for i in range(len(graph)):
                if v in graph[i]:
                    indegree = indegree + 1
            return indegree
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.