60 ms stack based recursive DFS Python


  • 0
    B
    class Solution(object):
        def canFinish(self, numCourses, prerequisites):
            """
            :type numCourses: int
            :type prerequisites: List[List[int]]
            :rtype: bool
            """
            adj_list = {x:[] for x in range( numCourses)}
            isVisited = [0]*numCourses
            stack = []
            
            if len(prerequisites) == 0:
                return True
            for x, y in prerequisites:
                adj_list[y].append(x)
                
            for node in adj_list:
                if isVisited[node] !=0 :
                    continue
                stack.append(node)
                while(stack):
                    currnode = stack[-1]
                    if isVisited[currnode] == 0:
                        isVisited[currnode] = 1
                    elif isVisited[currnode] == 1 or isVisited[currnode] == 2:
                        stack.pop()
                        isVisited[currnode] = 2
                        continue
                    for x in adj_list[currnode]:
                        if isVisited[x] == 0:
                            stack.append(x)
                        if isVisited[x] == 1:
                            return False
            return True

Log in to reply
 

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