Simple Python Cycle Detection


  • 0

    Keep two sets, Red and Black, then while visiting move the vertex into the Red set (the visiting set) then move the vertex to the Black set (the done set) once all its ancestors have been visited. If we run into a vertex that's currently in the Red set (not fully explored) it indicates that we've found a cycle. Since we're only dealing with #'s from 1 to n-1, we could use an array to indicate the visited status of each class at each index, but this will be better as it can be generalized to any set of classes

        def canFinish(self, numCourses, prerequisites):
            def cycle(v, G, R, B):
                if v in R: return True # cycle found
                R.add(v) # add to "Red" set
                if v in G:
                    for _v in G[v]:
                        if _v not in B and cycle(_v, G, R, B): return True # exit if DFS returns a cycle
                R.remove(v); B.add(v) # move from "Red" to "Black" set
                return False
            
            G, R, B = collections.defaultdict(list), set(), set()
            for p in prerequisites: # generate graph
                G[p[0]].append(p[1])
            for v in G:
                if v not in B and cycle(v, G, R, B): return False # cycle found
            return True # no cycle
    

Log in to reply
 

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