Leetcode # 210. Course Schedule II

https://leetcode.com/problems/course-schedule-ii/

Explanation

使用 in-degree

關鍵在於

1. 優先提取 in-degree 為 0 的 vertex（即該 vertex 已無任何前導 vertex）
2. vertex被提取時，調整其子 vertex 的 in-degree

當 graph 中有 loop

當 graph 中有 loop 時，
會導致 loop 中的 verteces 的 in-degree 無法被消除為 0，
並且此題則為無解

Solution

class Solution:
  def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
    adj_list = collections.defaultdict(list)
    in_degree = collections.Counter()
    for dest, src in prerequisites:
      adj_list[src].append(dest)
      in_degree[dest] += 1
      
    zero_indegree_queue = collections.deque([i for i in range(numCourses) if i not in in_degree])
    topological_sorted_order = []
    while zero_indegree_queue:
      vertex = zero_indegree_queue.popleft()
      topological_sorted_order.append(vertex)
      
      if vertex in adj_list:
        for neighbor in adj_list[vertex]:
          in_degree[neighbor] -= 1
          if in_degree[neighbor] == 0:
            zero_indegree_queue.append(neighbor)
    
    return topological_sorted_order if len(topological_sorted_order) == numCourses else []

Last Updated on 2023/08/16 by A1go