smj007

Course Schedule II

Aug 1st, 2025
106
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 2.02 KB | None | 0 0
  1. from collections import defaultdict, deque
  2. from typing import List
  3.  
  4. class Solution:
  5.     def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
  6.         """
  7.        This function returns the order in which courses should be taken
  8.        given a list of prerequisite pairs using Kahn's Algorithm for Topological Sorting.
  9.        If it's impossible to finish all courses due to a cycle, it returns an empty list.
  10.        """
  11.  
  12.         # Step 1: Build the graph
  13.         # premap maps each course to a list of courses that depend on it
  14.         # inorder keeps track of how many prerequisites each course has (in-degree)
  15.         premap = defaultdict(list)
  16.         inorder = defaultdict(int)
  17.  
  18.         for course, pre in prerequisites:
  19.             premap[pre].append(course)   # course depends on pre
  20.             inorder[course] += 1         # increase in-degree for the course
  21.  
  22.         # Step 2: Initialize queue with all courses that have no prerequisites (in-degree 0)
  23.         # These are the starting points for topological sort
  24.         q = deque([crs for crs in range(numCourses) if inorder[crs] == 0])
  25.  
  26.         # This list will store the final order of courses
  27.         order = []
  28.  
  29.         # Step 3: Perform BFS-based topological sort
  30.         while q:
  31.             # Remove a course that has no remaining prerequisites
  32.             current_course = q.popleft()
  33.             order.append(current_course)
  34.  
  35.             # Reduce the in-degree of all courses that depend on this course
  36.             for dependent_course in premap[current_course]:
  37.                 inorder[dependent_course] -= 1  # one prerequisite has been "taken"
  38.  
  39.                 # If a course now has no prerequisites, add it to the queue
  40.                 if inorder[dependent_course] == 0:
  41.                     q.append(dependent_course)
  42.  
  43.         # Step 4: Check if we were able to include all courses
  44.         # If not, it means there's a cycle and not all courses can be finished
  45.         return order if len(order) == numCourses else []
Advertisement
Add Comment
Please, Sign In to add comment