Share my solution in Python using topological sort


  • 0
    D
    from collections import defaultdict
    
    class Solution:
        # @param {integer} numCourses
        # @param {integer[][]} prerequisites
        # @return {boolean}
        def canFinish(self, numCourses, prerequisites):
            M, S = set(), set()
            edgesByEnd, edgesByStart = defaultdict(list), defaultdict(list)
            for edge in prerequisites:
                edgesByEnd[edge[0]].append(edge[1])   # edges using end node as key
                edgesByStart[edge[1]].append(edge[0]) # edges using start node as key
                M.add(edge[0])
                S.add(edge[1])
    
            S -= (S & M)    # S: nodes without incoming edges
            M -= S          # M: nodes with incoming edges
            while len(S) > 0:
                node = S.pop()
                for endNode in edgesByStart[node]:   # all nodes with incoming edge from node
                    startNodes = edgesByEnd[endNode]
                    startNodes.remove(node)          # remove edges coming from node
                    if len(startNodes) == 0:
                        del edgesByEnd[endNode]      # add nodes without incoming edge to S
                        S.add(endNode)
                    else:
                        edgesByEnd[endNode] = startNodes
                del edgesByStart[node]
    
            if len(edgesByEnd) > 0:     # if there are remaining edges, no topological order exists
                return False
            return True

Log in to reply
 

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