Python Topological Sort beats 98%


  • 0

    This solution is similar to others posted using BFS with an improvement. To speed up removal of outgoing edges I create an edgemap to look up outgoing edges without having to loop thru vertices or edges over and over again. I believe time complexity would be O(V+E).

    class Solution(object):
        def canFinish(self, numCourses, prereqs):
            inCount = [0 for i in range(numCourses)]
            edgemap = {i: [] for i in range(numCourses)}
            for e in prereqs:
                inCount[e[1]] += 1
                edgemap[e[0]].append(e[1])
            # Add courses with no prereqs to queue
            q = collections.deque(i for i in range(numCourses) if inCount[i]==0)
            count = 0
            while q:
                node = q.popleft()
                count += 1
                # Remove all outgoing edges
                for out in edgemap[node]:
                    inCount[out] -= 1
                    if inCount[out] == 0:
                        q.append(out)
            return count == numCourses            
    

Log in to reply
 

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