Python DFS solution for Course Schedule


  • 0
    A
    class Solution:
    # @param {integer} numCourses
    # @param {integer[][]} prerequisites
    # @return {boolean}
    def canFinish(self, numCourses, prerequisites):
        graph = {}
        for c, p in prerequisites:
            if c not in graph:
                graph[c] = []
            if p not in graph[c]:
                graph[c].append(p)
            
        course_taken = []
        required_done = lambda c: c in graph and all([req in course_taken for req in graph[c]])
        
        while len(graph):
            crawled = []
            c = graph.items()[0][0]
            stack = [c]
            while stack:
                c = stack.pop()
                if c in course_taken:
                    continue
                if c in crawled:
                    return False
                crawled.append(c)
                
                if c in graph:
                    r = graph[c]
                    stack.extend(r)
            
            while crawled:
                r = crawled.pop()
                if r in graph and not required_done(r):
                    continue
                if r not in course_taken:
                    course_taken.append(r)
                    if required_done(r):
                        del graph[r]
            
        return True

  • 0
    Z

    The problem declaration is ambiguous. If "one node is reachable only if ALL of its parents are reached",then detecting cycle solution is right. Else if "one node is reachable if ONE of its parent is reached", then solution can be much simpler, because you only need to find "independent nodes", and to see if they are connected to other nodes.


Log in to reply
 

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