Python DFS solution for Course Schedule

  • 0
    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]:
        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:
                if c in crawled:
                    return False
                if c in graph:
                    r = graph[c]
            while crawled:
                r = crawled.pop()
                if r in graph and not required_done(r):
                if r not in course_taken:
                    if required_done(r):
                        del graph[r]
        return True

  • 0

    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.