Python slow but easy to understand code with comments, not checking cycle


  • 0
    class Solution(object):
        def canFinish(self, numCourses, prerequisites):
            """
            :type numCourses: int
            :type prerequisites: List[List[int]]
            :rtype: bool
            """
            from collections import defaultdict
            graph = defaultdict(list)
            n = len(prerequisites)
            if n < 1:
                return True
            # courses that have prerequisites
            pre = []
            # convert to dict, key is the courses that have prerequisites, and the list is the prerequisites
            for i in prerequisites:
                graph[i[0]].append(i[1])
                pre.append(i[0])
            # courses that have prerequisites, make it set to remove duplicates
            pre = set(pre)
            if len(pre) == numCourses:
                return False
            # courses that can finish, initially are the ones that don't have prerequisites
            can_finish = set(range(numCourses)) - pre
            # flag to check if we add thing to can_finish 
            flag = True
            while flag:
                flag = False
                for i in graph:
                    # check if can_finish fulfill prerequisites of a course that not in can_finish 
                    if i not in can_finish:
                        # if the prerequisites list are all in can_finish, then add to can_finish 
                        if not (set(graph[i]) - can_finish):
                            flag = True
                            can_finish.add(i)
            
            return len(can_finish) == numCourses
    

Log in to reply
 

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