Simple Python solution using DFS

  • 1
    def findOrder(numCourses, prerequisites):
        def dfs(i, visited, graph, ret):
            #Stop visiting checked nodes
            if visited[i] == 1:
                return True
            #If cycle is detected, return False
            if visited[i] == -1:
                return False
            visited[i] = -1
            for n in graph[i]:
                if not dfs(n, visited, graph, ret):
                    return False
            #collecting results
            visited[i] = 1
            return True
        #Initializing graph data
        visited = [0] * numCourses
        graph = {x:[] for x in xrange(numCourses)}
        for p in prerequisites:
        #collecting topological order
        ret = []
        for i in xrange(numCourses):
            if not dfs(i, visited, graph, ret):
                return []
        return ret[::-1]

Log in to reply

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