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
Clean and commented Python solution
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.