Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- from collections import defaultdict, deque
- from typing import List
- class Solution:
- def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
- """
- This function returns the order in which courses should be taken
- given a list of prerequisite pairs using Kahn's Algorithm for Topological Sorting.
- If it's impossible to finish all courses due to a cycle, it returns an empty list.
- """
- # Step 1: Build the graph
- # premap maps each course to a list of courses that depend on it
- # inorder keeps track of how many prerequisites each course has (in-degree)
- premap = defaultdict(list)
- inorder = defaultdict(int)
- for course, pre in prerequisites:
- premap[pre].append(course) # course depends on pre
- inorder[course] += 1 # increase in-degree for the course
- # Step 2: Initialize queue with all courses that have no prerequisites (in-degree 0)
- # These are the starting points for topological sort
- q = deque([crs for crs in range(numCourses) if inorder[crs] == 0])
- # This list will store the final order of courses
- order = []
- # Step 3: Perform BFS-based topological sort
- while q:
- # Remove a course that has no remaining prerequisites
- current_course = q.popleft()
- order.append(current_course)
- # Reduce the in-degree of all courses that depend on this course
- for dependent_course in premap[current_course]:
- inorder[dependent_course] -= 1 # one prerequisite has been "taken"
- # If a course now has no prerequisites, add it to the queue
- if inorder[dependent_course] == 0:
- q.append(dependent_course)
- # Step 4: Check if we were able to include all courses
- # If not, it means there's a cycle and not all courses can be finished
- return order if len(order) == numCourses else []
Advertisement
Add Comment
Please, Sign In to add comment