207. Course Schedule - cocoder39/coco39_LC GitHub Wiki

207. Course Schedule

Option 1 - DFS approach: this is an approach used to detect cycle in directed graph (see reference)

• visited is used to avoid redundant checks: eg b->a, c->b, then we can avoid re-checking b
• path is used to detect loop:
  • to maintain a recursion stack we need to use back track
  • if there is cycle in a recursion stack, then there is loop

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        pre_to_next = collections.defaultdict(list)
        for next_course, pre_course in prerequisites:
            pre_to_next[pre_course].append(next_course)
        
        visited = [False] * numCourses
        in_stack = [False] * numCourses
        for course in range(numCourses):
            if not visited[course]:
                # in_stack = [False] * numCourses, same effect putting it here or up as there is backtrack. up is more efficient
                if self.hasCycle(course, pre_to_next, in_stack, visited):
                    return False
        return True
    
    def hasCycle(self, cur: int, pre_to_next: Dict[int, int], in_stack: List[bool], visited: List[bool]) -> bool:
        visited[cur] = True
        in_stack[cur] = True

        for next_course in pre_to_next[cur]:
            if in_stack[next_course]: # in currrent recurision stack
                return True
            elif not visited[next_course] and self.hasCycle(next_course, pre_to_next, in_stack, visited):
                return True
        in_stack[cur] = False
        return False

Option 2: topological sort

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        adjacent_list = collections.defaultdict(list)
        in_degrees = collections.defaultdict(int)
        for prerequisite in prerequisites:
            adjacent_list[prerequisite[1]].append(prerequisite[0])
            in_degrees[prerequisite[0]] += 1
            in_degrees[prerequisite[1]] += 0
            
        queue = collections.deque()
        for key in in_degrees:
            if in_degrees[key] == 0:
                queue.append(key)
        
        count = 0
        while queue:
            i = queue.popleft()
            count += 1
            for j in adjacent_list[i]:
                in_degrees[j] -= 1
                if in_degrees[j] == 0:
                    queue.append(j)
        
        return len(in_degrees) == count

Complexity: E is #edges and V is #vertexes in graph.

• Step 1: building graph O(E) time complexity. O(E+V) space complexity for adjacent_list and O(V) space complexity for in_degrees
• Step 2: iterate in-degree dict O(V)
• Step 3: BFS visits each vertex and each edge once O(E + V)

Total time complexity is O(E + V), space complexity is O(E+V)