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].append(edge) # 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
My python DFS recursive solution (same algorithm for #207 and #210)
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.