Python DFS: combine cycle detection and topological order together.


  • 0
    S
    class Solution(object):
        def findOrder(self, numCourses, prerequisites):
            """
            :type numCourses: int
            :type prerequisites: List[List[int]]
            :rtype: List[int]
            """
            # build a graph in adjacent list form
            g = [[] for _ in range(numCourses)]
            for v, w in prerequisites:
                # w->v
                g[w].append(v)
            # 1. check cycles with DFS
            # 2. topological sort: <-- reverse post-order traversal
            on_stack = [False] * numCourses
            marked = [False] * numCourses
            order = []
            
            def dfs(v):
                """
                Return True if there is any cycle; otherwise, False.
                """
                on_stack[v] = True
                marked[v] = True
                for w in g[v]:
                    if not marked[w]: # if w is not marked, then it cannot be on stack
                        if dfs(w):
                            return True 
                    elif on_stack[w]: # a path from w ---> v
                        return True
                on_stack[v] = False
                order.append(v)	# post-order visit
                return False
            
            # there may be multiple disjoint subgraphs
            for v in range(numCourses):
                if not marked[v]:
                    if dfs(v): # if there is any cycle
                        return []
            return list(reversed(order)) # reverse post-order

Log in to reply
 

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