Python BFS/DFS solutions with comments.


  • 9
    C
    # BFS: from the end to the front
    def canFinish1(self, numCourses, prerequisites):
        forward = {i: set() for i in xrange(numCourses)}
        backward = collections.defaultdict(set)
        for i, j in prerequisites:
            forward[i].add(j)
            backward[j].add(i)
        queue = collections.deque([node for node in forward if len(forward[node]) == 0])
        while queue:
            node = queue.popleft()
            for neigh in backward[node]:
                forward[neigh].remove(node)
                if len(forward[neigh]) == 0:
                    queue.append(neigh)
            forward.pop(node)
        return not forward  # if there is cycle, forward won't be None
    
    # BFS: from the front to the end    
    def canFinish2(self, numCourses, prerequisites):
        forward = {i: set() for i in xrange(numCourses)}
        backward = collections.defaultdict(set)
        for i, j in prerequisites:
            forward[i].add(j)
            backward[j].add(i)
        queue = collections.deque([node for node in xrange(numCourses) if not backward[node]])
        count = 0
        while queue:
            node = queue.popleft()
            count += 1
            for neigh in forward[node]:
                backward[neigh].remove(node)
                if not backward[neigh]:
                    queue.append(neigh)
        return count == numCourses
        
    # DFS: from the end to the front
    def canFinish3(self, numCourses, prerequisites):
        forward = {i: set() for i in xrange(numCourses)}
        backward = collections.defaultdict(set)
        for i, j in prerequisites:
            forward[i].add(j)
            backward[j].add(i)
        stack = [node for node in forward if len(forward[node]) == 0]
        while stack:
            node = stack.pop()
            for neigh in backward[node]:
                forward[neigh].remove(node)
                if len(forward[neigh]) == 0:
                    stack.append(neigh)
            forward.pop(node)
        return not forward
            
    # DFS: from the front to the end    
    def canFinish(self, numCourses, prerequisites):
        forward = {i: set() for i in xrange(numCourses)}
        backward = collections.defaultdict(set)
        for i, j in prerequisites:
            forward[i].add(j)
            backward[j].add(i)
        stack = [node for node in xrange(numCourses) if not backward[node]]
        while stack:
            node = stack.pop()
            for neigh in forward[node]:
                backward[neigh].remove(node)
                if not backward[neigh]:
                    stack.append(neigh)
            backward.pop(node)
        return not backward

  • 0
    P

    Hi, can you help me to spot what is wrong with my code, which cannot pass the test-case of 2000 courses.
    Thanks!

    import collections
    class Solution(object):
        def canFinish(self, numCourses, prerequisites):
            if not numCourses:
                return False
            elif not prerequisites:
                return True
            else:
                require = collections.defaultdict(list) # to save prerequisites
                for pair in prerequisites:
                    require[pair[0]].append(pair[1])
                path = []
                for i in xrange(numCourses):
                    if not self.DFS(i, require, path):
                        return False
                return True
                
        def DFS(self, i, require, path):
            # do DFS for i
            if i in path: return False # cycle
            for j in require[i]:
                if not self.DFS(j, require, path + [i]):
                    return False
            return True

  • 0
    C

    You answer seems correct but "Time Limit Exceeded". It should be better if can change your code to iterative dfs by using explicit stack instead of using recursion.


  • 0
    P

    sure. Thank you so much!


Log in to reply
 

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