Python 20 lines DFS solution sharing with explanation


  • 38
    R
    def canFinish(self, numCourses, prerequisites):
        graph = [[] for _ in xrange(numCourses)]
        visit = [0 for _ in xrange(numCourses)]
        for x, y in prerequisites:
            graph[x].append(y)
        def dfs(i):
            if visit[i] == -1:
                return False
            if visit[i] == 1:
                return True
            visit[i] = -1
            for j in graph[i]:
                if not dfs(j):
                    return False
            visit[i] = 1
            return True
        for i in xrange(numCourses):
            if not dfs(i):
                return False
        return True
    
    1. if node v has not been visited, then mark it as 0.
    2. if node v is being visited, then mark it as -1. If we find a vertex marked as -1 in DFS, then their is a ring.
    3. if node v has been visited, then mark it as 1. If a vertex was marked as 1, then no ring contains v or its successors.

    References: daoluan.net


  • 0
    S

    great idea ! thanks for sharing


  • 0

    at the first glance, i think u can use memo to improve, however, when i realize that u use visit array as implicit memo i know this is a great trick, thanks~


  • 0

    @rodolphe Could be cleaner code. Check this out.

    class Solution(object):
        def canFinish(self, n, edges):
            graph = {i:set() for i in range(n)}
            indeg = {i:0     for i in range(n)}
            for s, e in set(tuple(x) for x in edges):
                graph[s] |= {e}
                indeg[e] += 1
            queue  =  [i for i in range(n) if not indeg[i]]
            visits =  set(queue) 
            for node in queue:
                for neigh in graph[node]:
                    if neigh in visits: 
                        return False
                    indeg[neigh] -= 1
                    if not indeg[neigh]:
                        visits.add(neigh)
                        queue += neigh,
            return len(visits) == n
    

  • 5
    H

    This solution might be longer, but it is slightly easier to read. Comments are in-line. Thanks.

    class Solution(object):
        def canFinish(self, numCourses, prerequisites):
            """
            :type numCourses: int
            :type prerequisites: List[List[int]]
            :rtype: bool
            """
            graph = [[] for _ in range(numCourses)]
            visited = [0 for _ in range(numCourses)]
            # create graph
            for pair in prerequisites:
                x, y = pair
                graph[x].append(y)
            # visit each node
            for i in range(numCourses):
                if not self.dfs(graph, visited, i):
                    return False
            return True
        
        def dfs(self, graph, visited, i):
            # if ith node is marked as being visited, then a cycle is found
            if visited[i] == -1:
                return False
            # if it is done visted, then do not visit again
            if visited[i] == 1:
                return True
            # mark as being visited
            visited[i] = -1
            # visit all the neighbours
            for j in graph[i]:
                if not self.dfs(graph, visited, j):
                    return False
            # after visit all the neighbours, mark it as done visited
            visited[i] = 1
            return True
    
    

  • 1

    @hanfang.cshl
    why you do have to use -1 , 1 and 0 in visited array?
    In other words,
    Why do you divide it into being visited, visiting neighbours, done visited?
    Is there any way to use 1 or 0 in the visited array to solve this problem?


  • 2
    F

    @rodolphe Nice DFS algorithm! A small modification is possible, though:
    the last four lines can be combined into

    return all(dfs(i) for i in xrange(numCourses))
    

  • 0
    G

    @agave Very cool! But i think what you described is Kahn's algorithm, not DFS... https://en.wikipedia.org/wiki/Topological_sorting#Kahn.27s_algorithm


  • 0
    S

    @Zura -1 means this node is part of the current trip. if you see it again, it's a cycle. 1 means a dfs has been done starting from this node, and no cycle was found. if you hit this, going down this path won't find any cycles


Log in to reply
 

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