python topological sort beat 98.9%


  • 0

    Here You Should Know

    1.Every time you try to remove all the points that in-degree is 0,there always exists new point whose in-degree is 0, you could add that into the stack/queue
    2.The stack is much more efficient because you pop from the tail which expense very little

    class Solution(object):
        def findOrder(self,numCourses,prerequisites):
            outlist=[[] for _ in range(numCourses)]
            inlist=[0 for _ in range(numCourses)]
            for p in prerequisites:
                outlist[p[1]].append(p[0])
                inlist[p[0]]+=1
            stack=[]
            res=[]
            for p in range(len(inlist)):
                #print p
                if inlist[p]==0:stack.append(p)
            #print stack
            while len(stack)>0:
                c=stack.pop(0)
                res.append(c)
                for x in outlist[c]:
                    inlist[x]-=1
                    if inlist[x]==0:
                        stack.append(x)
            if len(res)<numCourses:return[]
            return res
    

Log in to reply
 

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