Fast python DFS solution with inline explanation

• 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

• 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

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