Concise 10-liner using DFS cycle detection


  • 0
    O
    class Solution(object):
        def canFinish(self, numCourses, prerequisites):
            color, edges = [0]*numCourses, [[] for _ in range(numCourses)]
            for start,end in prerequisites:
                edges[start].append(end)
            def hasCycle(node):
                color[node] = 1
                if any(color[n]==1 or color[n]==0 and hasCycle(n) for n in edges[node]):
                    return True
                color[node] = 2
                return False
            return not any(hasCycle(n) for n in range(numCourses) if color[n]==0)
    

    Which is equivalent to:

    class Solution(object):
        def canFinish(self, numCourses, prerequisites):
            color = [0] * numCourses
            edges = [[] for _ in range(numCourses)]
            for start,end in prerequisites:
                edges[start].append(end)
                
            def hasCycle(node):
                color[node] = 1
                for n in edges[node]:
                    if color[n] == 1:
                        return True
                    if color[n] == 0 and hasCycle(n):
                        return True
                color[node] = 2
                return False
                
            for n in range(numCourses):
                if color[n] == 0:
                    if hasCycle(n):
                        return False
            return True
    

Log in to reply
 

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