Clean and commented Python solution


  • 1
    T
    class Solution(object):
        """
            This is similar to finding a cycle in a graph and at the same time,
            doing a Topological sort of the vertices. The approach here uses DFS.
        """
        def findOrder(self, numCourses, prerequisites):
            """
            :type numCourses: int
            :type prerequisites: List[List[int]]
            :rtype: List[int]
            """
            #If there are no dependencies among courses, they can 
            #be taken in any order. Weird input/output case tbh.
            if prerequisites == []:
                return [i for i in xrange(numCourses)]
            
            #Convert the edges into an adjecency list representation
            self.adj = [set() for i in xrange(numCourses)]
            
            for i,j in prerequisites:
                self.adj[j].add(i)
            
            #visited set will track vertices seen while exploring the current vertex
            self.visited = set()
            
            #completed set will track vertices that have been completely explored
            self.completed = set()
            
            self.res = []
            
            #For every vertex that has not been explored, visit it
            for i in xrange(len(self.adj)):
                if i not in self.visited and i not in self.completed:
                    possible = self.visit(i)
                    
                    #visit() returns False if a cycle is detected
                    if not possible:
                        return []
            
            #Topological sort is the reverse of the order in which the 
            #vertices were explored
            return self.res[::-1]
            
        def visit(self, u):
            #mark the current vertex as visited
            self.visited.add(u)
            possible = True
            
            #For every vertex adjecent to v
            for v in self.adj[u]:
                
                #explore the vertex only if not already explored
                if v not in self.visited and v not in self.completed:
                    possible = possible and self.visit(v)
                
                #if this vertex was seen during the exploration of current vertex,
                #then there is a cycle in the graph and we can return False
                if v in self.visited:
                    possible = False
                    break
                
            #finally, we can mark the current vertex as completely explored
            self.visited.remove(u)
            self.completed.add(u)
            
            #If no cycles were found, we can add current vertex to sort order
            if possible:
                self.res.append(u)
                
            return possible

Log in to reply
 

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