python dfs with topological sort


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

Log in to reply
 

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