Concise python solution


  • 0
    I
    from collections import defaultdict
    
    class Solution(object):
        def findOrder(self, numCourses, prerequisites):
            """
            :type numCourses: int
            :type prerequisites: List[List[int]]
            :rtype: List[int]
            """
            def dfs_has_cycle(vertex):
                visited[vertex] = 1
                
                for neighbor in adj_list[vertex]:
                    if visited[neighbor] == 1:
                        return True
                    elif visited[neighbor] == 0 and dfs_has_cycle(neighbor):
                        return True
                        
                ordering.append(vertex)
                visited[vertex] = 2
                return False
            
            if prerequisites == []:
                return range(numCourses)
                
            adj_list = defaultdict(list)
            for prereq in prerequisites:
                adj_list[prereq[1]].append(prereq[0])
                
            visited = [0 for i in xrange(numCourses)]
            ordering = []
    
            for vertex in xrange(numCourses):
                if not visited[vertex] and dfs_has_cycle(vertex):
                    return []
                
            return ordering[::-1]
            
    

Log in to reply
 

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