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

• ``````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``````

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