Fast and easy Python Solution


  • 0
    R
    ## Directed Graph
    # graph: dict(k: int, v: set) to store the forward coureses for each course. e.g [0,1] -> graph[1] = set(0)
    # preCouresNum: list store the number of prerequistes for each course. Value shall be updated in iteration. e.g [0,1],[2,1] -> [1,0,1]
    # available: a FIFO queue(list actullay) that stores current available courses. Course will be removed from head once it has been visited.
    # 1. build graph, preCouresNum. 2. build initial available queue from preCourseNum. 3. dequeue each course and minues the preCourseNum value by one for each reachable cosuse. 4. if a reachable cosuse's preCourseNum equals zero, add it to the available queue. 5. Go back to step 3 if avaiable queue is not empty. 6. return True is sum of preCourseNum is zero. 
    
    def canFinish(self, numCourses, prerequisites):
        """
        :type numCourses: int
        :type prerequisites: List[List[int]]
        :rtype: bool
        """
        graph = collections.defaultdict(set)
        preCourseNum = [0]*numCourses
        for pair in prerequisites:
            if pair[0] not in graph[pair[1]]:
                graph[pair[1]].add(pair[0])
                preCourseNum[pair[0]] += 1
        available = [i for i,v in enumerate(preCourseNum) if v == 0]
        while len(available) !=0:
            course = available[0]
            del available[0]
            for possible in graph[course]:
                preCourseNum[possible] -= 1
                if preCourseNum[possible] == 0:
                    available.append(possible)
        return sum(preCourseNum)==0

Log in to reply
 

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