Python DFS for Topological Sort in O(V+E)


  • 0
    A
    from collections import defaultdict
    class Solution:
    # @param {integer} numCourses
    # @param {integer[][]} prerequisites
    # @return {integer[]}
    def findOrder(self, numCourses, prerequisites):
        self.matrix = defaultdict(list)
        for edge in prerequisites:
            end, beg = edge
            self.matrix[beg].append(end)
        
        self.visit = [0] * numCourses
        self.cycle = False
        self.answer = []
        for i in xrange(numCourses):
            if self.visit[i] == 0:
                self.dfs(i)
            if self.cycle:
                return []
        return self.answer[::-1]
    
    def dfs(self, now):
        if self.cycle:
            return
        
        if self.visit[now] == 1: # cycle
            self.cycle = True
            return
        if self.visit[now] == 2:
            return
        
        self.visit[now] = 1
        for i in self.matrix[now]:
            self.dfs(i)
        self.visit[now] = 2
        
        self.answer.append(now)
        return

Log in to reply
 

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