Python DFS modified Topsort


  • 1

    Top sort with added cycle detection. Append on any vertices that lack indegrees at the end

        def findOrder(self, numCourses, prerequisites):
    
            def traverse(v, G, R, B, deque):
                if v in R: return False
                R.add(v)
                if v in G:
                    for _v in G[v]:
                        if _v not in B and not traverse(_v, G, R, B, deque): return False
                R.remove(v); B.add(v)
                deque.appendleft(v)
                return True
            
            G, R, B, deque = collections.defaultdict(list), set(), set(), collections.deque()
            for p in prerequisites:
                G[p[1]].append(p[0])
            for v in G:
                if v not in B and not traverse(v, G, R, B, deque): return []
            for i in range(numCourses):
                if i not in B: deque.append(i)
            return list(deque)
    

Log in to reply
 

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