Fast python DFS solution with inline explanation


  • 8
    P

    Runs takes 80ms

    class Solution:
        # @param {integer} numCourses
        # @param {integer[][]} prerequisites
        # @return {integer[]}
        def findOrder(self, numCourses, prerequisites):
            # use DFS to parse the course structure
            self.graph = collections.defaultdict(list) # a graph for all courses
            self.res = [] # start from empty
            for pair in prerequisites:
                self.graph[pair[0]].append(pair[1]) 
            self.visited = [0 for x in xrange(numCourses)] # DAG detection 
            for x in xrange(numCourses):
                if not self.DFS(x):
                    return []
                 # continue to search the whole graph
            return self.res
        
        def DFS(self, node):
            if self.visited[node] == -1: # cycle detected
                return False
            if self.visited[node] == 1:
                return True # has been finished, and been added to self.res
            self.visited[node] = -1 # mark as visited
            for x in self.graph[node]:
                if not self.DFS(x):
                    return False
            self.visited[node] = 1 # mark as finished
            self.res.append(node) # add to solution as the course depenedent on previous ones
            return True

  • 0
    W

    Great idea.
    My iteration version:

    class Solution(object):
    def findOrder(self, numCourses, prerequisites):
        """
        :type numCourses: int
        :type prerequisites: List[List[int]]
        :rtype: List[int]
        """
        res = []
        graph = collections.defaultdict(list) # a graph for all courses
        for pre in prerequisites:
            graph[pre[0]].append(pre[1])
        visited = [0 for _ in xrange(numCourses)] 
        # -1: visited
        # 0~: iteration pointer
        stack = []
        for x in xrange(numCourses):
            if visited[x] == -1: continue
            stack.append(x)
            while stack:
                tmp = stack[-1]
                v = visited[tmp]
                visited[tmp] += 1
                if v < len(graph[tmp]):
                    pre = graph[tmp][v]
                    if visited[pre] == 0:
                        stack.append(pre)
                    elif visited[pre] > 0:
                        return []
                else:
                    res.append(stack.pop())
                    visited[tmp] = -1
        return res

Log in to reply
 

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