Python DFS Topological Sort


  • 0
    R
    def findOrder(self, numCourses, prerequisites):
        graph = collections.defaultdict(list)
        for c, p in prerequisites:
            graph[c].append(p)
        
        ret = []
        def dfsTopSort(c, completed, current):
            # return False if a cycle is detected
            if c in current:
                return False    # cycle
            current.add(c)
            for p in graph[c]:
                if p in completed:
                    continue
                if not dfsTopSort(p, completed, current):
                    return False
            completed.add(c)
            ret.append(c)
            return True
            
        completed = set()
        for c in range(numCourses):
            if c in completed:
                continue
            if not dfsTopSort(c, completed, set()):
                return []
        return ret
    

Log in to reply
 

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