Straight Cormen DFS beats 90% of Python submissions


  • 0
    J
    def canFinish(self, numCourses, prerequisites):
        # find if there is a cycle in this directed graph
        # use Cormen DFS and check if node has been visited before (gray), i.e., is a back edge
        if not prerequisites:
            return True
        Adj = {i:[] for i in xrange(numCourses) } # Adjacency list
        for edge in prerequisites:
            Adj[edge[1]].append(edge[0])
        # just need color
        V = numCourses*[0]
        for i in xrange(numCourses):
            if V[i] == 0:
                if not self.DFSvisit(i,Adj,V):
                    return False
        return True
        
    def DFSvisit(self, u, Adj, V):
        V[u] = 1
        for v in Adj[u]:
            if V[v] == 1:
                return False
            if V[v] == 0:
                if not self.DFSvisit(v,Adj,V):
                    return False
        V[u] = 2
        return True

Log in to reply
 

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