Python Topological Sort


  • 0
    class Solution(object):
        def findOrder(self, numCourses, prerequisites):
            pre, suc = collections.defaultdict(set), collections.defaultdict(set)
            for p in prerequisites:
                if p[1] in suc[p[0]]:
                    return []
                pre[p[0]].add(p[1])
                suc[p[1]].add(p[0])
            all = set()
            for i in xrange(numCourses):
                all.add(i)
            q = all - set(pre.keys())
            ans = []
            while q:
                f = q.pop()
                ans.append(f)
                lst = suc[f]
                for l in lst:
                    pre[l].remove(f)
                    if len(pre[l]) == 0:
                        del pre[l]
                        q.add(l)
            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.