Simple BFS linear time solution, 14 line, intuitive with comments


  • 0
    H
    class Solution:
        # @param {integer} numCourses
        # @param {integer[][]} prerequisites
        # @return {boolean}
        def canFinish(self, numCourses, prerequisites):
            # BFS with linear O(V+E) time and space
            # Incoming Edge Set: In[n]: set of courses that need to be finished before couse n
            # Outgoing Edge Set: Out[n]: set of courses that need to be finished after course n
            In =  [set() for n in range(numCourses)] 
            Out = [set() for n in range(numCourses)]
            for pair in prerequisites:
                In[pair[0]].add(pair[1])
                Out[pair[1]].add(pair[0]) #
                
            # Find and start with all nodes with no incoming edges
            import collections
            Q = collections.deque([n for n in range(numCourses) if not In[n]])
            while Q: 
                cur = Q.pop()
                while Out[cur]:
                    # remove all outgoing edges: cur->nex
                    nex = Out[cur].pop()
                    In[nex].remove(cur)
                    # if nex has no other incoming edges, it is safe to finish nex
                    if not In[nex]:
                        Q.append(nex)
            # All nodes visited in order = nothing left in the adjacency list
            return False if any(Out) else True

Log in to reply
 

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