Python solution using dfs


  • 1
    S
    This solution is based on an article in geeksforgeeks http://www.geeksforgeeks.org/detect-cycle-in-a-graph/
    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:
                d[prerequisite[1]].append(prerequisite[0])
            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:
            visited.add(course)
            stack.add(course)
            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
        stack.remove(course)
        return False

Log in to reply
 

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