Python DFS version


  • 0
    R
    def canFinish(self, numCourses, prerequisites):
        """
        :type numCourses: int
        :type prerequisites: List[List[int]]
        :rtype: bool
        """
        if (len(prerequisites)) == 0:
            return True
            
        maps = [[] for i in range(numCourses)]
        outdegree = [0  for i in range(numCourses)]
        iters = set()
        for req in prerequisites:
            if len(maps[req[1]]) != 0:
                iters.add(req[1])
            maps[ req[0] ].append(req[1])
            outdegree[ req[0] ] += 1
            
    
        iters = list(iters)
        for u in iters:
            visited = []
            if outdegree[u] != 0:
                if dfs(u, visited, maps, outdegree):
                    return False
            
        return True
    

    def dfs(u, visited, maps, outdegree):
    
        visited.append(u)
        outdegree[u] -= 1
            
        for v in maps[u]:
            if v in visited:
                return True
            else:
                if dfs(v, visited, maps, outdegree):
                    return True
     
        visited.pop()
        return False
    

    This is DFS version code... Thanks.


Log in to reply
 

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