Why does my Python solution only fails the last test case 33/34


  • 0
    1

    My Python DFS solution passes 33/34 test cases, the last test case has 500 courses so I could not paste the input here. Could anyone take a look at my code and see if there is a logical flaw. I hope the code is well documented. Thanks!

    class Solution(object):
        def canFinish(self, numCourses, prerequisites):
            """
            :type numCourses: int
            :type prerequisites: List[List[int]]
            :rtype: bool
            """
            global vertices, cycle
            # special case
            if prerequisites == []:
                return True
            vertices = {}  # store node and a list of its neigobors; such as key --> value (do key first, then value)
            cycle = False  # a global flag, if a cycle is detected, set it to True
            
            # initialize the vertices dictionary
            for pair in prerequisites:
                if pair[1] not in vertices:
                    vertices[pair[1]] = [pair[0]]
                else:
                    vertices[pair[1]].append(pair[0])
            
            
            # we do a DFS here
            return not self.helper(prerequisites[0][1], set([]))
            
        def helper(self, node, stack):
            """An implementation of DFS
               node is the current node to be explored
               stack is a list of nodes to be revisited (we haven't explored all of their neighbors yet so we store them into a set)
            """
            global cycle
            if cycle == True:
                # don't need to go further, because we know there is at least one cycle
                return cycle
            if node in vertices:
                # start exploring this node
                stack.add(node)
                for neighbor in vertices[node]:
                    if neighbor in stack:
                        # we have seen neighbor before, there is a cycle!
                        cycle = True
                    self.helper(neighbor, stack)
                # finish exploring this node
                stack.remove(node)
            return cycle

  • 1
    Z

    I meet the same mistake with you, If you find the answer, could you tell me? Thank you very much


Log in to reply
 

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