Python DFS version

  • 0
    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:
            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):
        outdegree[u] -= 1
        for v in maps[u]:
            if v in visited:
                return True
                if dfs(v, visited, maps, outdegree):
                    return True
        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.