Python Topological Sort


  • 0
    class Solution(object):
        def findOrder(self, numCourses, prerequisites):
            indegree, outdegree = collections.defaultdict(set), collections.defaultdict(set)
            for x, y in prerequisites:
                outdegree[y].add(x)
                indegree[x].add(y)
            zero_degree = []
            for i in range(numCourses):
                if not indegree[i]:
                    zero_degree.append(i)
            i = 0
            while i < len(zero_degree):
                node = zero_degree[i]
                for x in outdegree[node]:
                    indegree[x].remove(node)
                    if not indegree[x]:
                        zero_degree.append(x)
                i += 1
            return zero_degree if i == numCourses else []

Log in to reply
 

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