Python Topological Sort (beats 93%)


  • 0
    class Solution(object):
        def findOrder(self, numCourses, prerequisites):
            indegree,graph,ans = [0]*numCourses,[[] for _ in xrange(numCourses)],[]
            for y,x in prerequisites:
                indegree[y] += 1
                graph[x] += y,
            q = collections.deque([i for i in xrange(numCourses) if indegree[i]==0])
            while q:
                x = q.pop()
                for y in graph[x]:
                    indegree[y] -= 1
                    if indegree[y]==0:
                        q.append(y)
                ans += x,
            return ans if len(ans)==numCourses else []

Log in to reply
 

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