Python Solution with Detailed Explanation


  • 0
    G

    Solution

    Course Schedule https://leetcode.com/problems/course-schedule/

    3 State Array Solution using DFS: O(V + E)

    • We just need to detect a cycle in this problem. The algorithm we use is a variant of DFS where we color the node as 0(unvisited), 1(visiting), and 2(visited). We can maintain a state array to maintain the status of the nodes. While doing a DFS for a node X, we mark it as visiting (1). Before we complete the DFS for this node, if we encounter a back-edge, i.e. another node Y with neighbor X, we detect a cycle.
    class Solution(object):
        def canFinish(self, numCourses, prerequisites):
            """
            :type numCourses: int
            :type prerequisites: List[List[int]]
            :rtype: bool
            """
            graph = {}
            for v in range(numCourses):
                graph[v] = []
            for pre in prerequisites:
                graph[pre[0]].append(pre[1])
            return not self.detect_cycle(graph, numCourses)
        
        def detect_cycle(self, g, n):
            state = [0]*n
            for i in range(n):
                if state[i] == 0: # If the node is unvisited.
                    if self.detect(g, i, state):
                        return True
            return False
        
        def detect(self, g, i, state):
            state[i] = 1 # Mark the node in visiting status.
            for nbr in g[i]:
                if state[nbr] == 1: # We found a back edge! Return True.
                    return True
                elif state[nbr] == 0: # Do DFS only if you find an unvisited neighbor
                    if self.detect(g, nbr, state):
                        return True
            state[i] = 2 # Mark the node as visited
            return False
    

    Visited and Visiting Set Solution using DFS: O(V+E)

    • Now we can implement this algorithm using 2 sets: visiting and visited.
    • Notice the choice of API. detect_cycle will return T for a cycle & F for no cycle.
    • Just remember to remove the node from visiting after you have completed DFS. Example; 2, [1,0]. You will start with node 0 and add to visiting but not remove it. Then when you start with node 1, you will find its neighbor node 0 in visiting set and incorrectly mark a cycle.
    • Note when we call detect recursively within detect, we do collect its output result and process it appropriately.
    class Solution(object):
        def canFinish(self, numCourses, prerequisites):
            """
            :type numCourses: int
            :type prerequisites: List[List[int]]
            :rtype: bool
            """
            graph = {}
            for v in range(numCourses):
                graph[v] = []
            for pre in prerequisites:
                graph[pre[0]].append(pre[1])
            return not self.detect_cycle(graph, numCourses)
        
        def detect_cycle(self, g, n):
            visiting, visited = set([]), set([])
            for i in range(n):
                if i not in visited:
                    if self.detect(g, i, visiting, visited):
                        return True
            return False
        
        def detect(self, g, i, visiting, visited):
            visited.add(i)
            visiting.add(i)
            for nbr in g[i]:
                if nbr in visiting:
                    return True
                elif nbr not in visited:
                    if self.detect(g, nbr, visiting, visited):
                        return True
            visiting.remove(i)
            return False
    

Log in to reply
 

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