My python DFS recursive solution (same algorithm for #207 and #210)


  • 1
    class Solution(object):
    def findOrder(self, numCourses, prerequisites):
        """
        :type numCourses: int
        :type prerequisites: List[List[int]]
        :rtype: List[int]
        """
        course_array = [[] for i in xrange(numCourses)] # each sub-list records the pre-requisites
        visit = [0 for i in xrange(numCourses)]         # check whether these is a loop
        res = []                                        # the course ordering for #210
        for edge in prerequisites:
            course_array[edge[0]].append(edge[1])
    
        # For #210, put courses that don't need prerequisites into ordering.
        i = 0
        while i < numCourses:
            if len(course_array[i]) == 0:
                res += i,               # add into ordering.
                visit[i] = -1           # visited.
            i += 1
    
        def dfs(x, res):
            # find out this course is in a loop or not
            # True => in a loop => invalid course
            if visit[x] == -1:          # visit here earlier, there's no loop.
                return False
            if visit[x] == 1:           # there's a loop!
                return True
    
            visit[x] = 1                # begin to check this node and its prerequisite
            for v in course_array[x]:
                if dfs(v, res):
                    return True
            visit[x] = -1               # check PASSED, add this course into ordering. 
            res.append(x)               # For #210, Here prerequisite will be added earlier.
            return False
    
        # begin from the root
        for i in xrange(numCourses):
            if dfs(i, res):
                return []           # if there's a loop => NOT possible to complete.
        
        return res        # In #207, just return True

Log in to reply
 

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