Python solution using dfs

  • 1
    This solution is based on an article in geeksforgeeks
    class Solution(object):
        def canFinish(self, numCourses, prerequisites):
            :type numCourses: int
            :type prerequisites: List[List[int]]
            :rtype: bool
            d = collections.defaultdict(list)
            for prerequisite in prerequisites:
            visited = set()
            stack = set()
            for course in d:    
                if course not in visited and dfs(course, visited, d, stack):
                    return False
            return True
    def dfs(course, visited, d, stack):  
        if course not in visited:
            neighbors = d[course] if course in d else []
            for neighbor in neighbors:
                if neighbor not in visited:
                    if dfs(neighbor, visited, d, stack):
                        return True
                elif neighbor in stack:
                    return True
        return False

Log in to reply

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