# python dfs with topological sort

• ``````from collections import defaultdict
class Solution(object):

def findOrder(self, numCourses, prerequisites):
self.numCourses = numCourses
self.visited = [False for _ in range(numCourses)]
self.stack = []

if prerequisites == []:
return list(range(numCourses))

#first create an adjacency list to represent the graph
self.graph = defaultdict(list)
for prereq in prerequisites:
pre = prereq[0]
course = prereq[1]
self.graph[course].append(pre)

#print(self.graph)
for node in range(numCourses):
ans = self.dfs(node, self.visited, self.stack)
if not ans:
return [] #return an empty list if there is no solution

return self.stack

#this is actually a topological sort using dfs
def dfs(self, node, visited, stack):
#print(node, visited)
if visited[node] == True: #loop detected
return False

if visited[node] == "good":
return True

visited[node] = True

#print("stack",stack)
for next_node in self.graph[node]:
print("node,next", node, next_node)
if not self.dfs(next_node, visited, stack):
return False

stack.insert(0,node)
visited[node] = "good"
# after reaching the end,
# you can mark the node as good,
# it has already been verified as not having a loop

return True``````

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