Leetcode 207 : Course Schedule (Solution in Python ) : Topological Sort

Link to Question: https://leetcode.com/problems/course-schedule/

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        courses=collections.defaultdict(set)
        preq=collections.defaultdict(set)
        for u,v in prerequisites:
            courses[v].add(u)
            preq[u].add(v)
        nopreq=[i for i in range(numCourses) if not preq[i]]
        count=0
        while nopreq:
            np=nopreq.pop()
            for child in courses[np]:
                preq[child].remove(np)
                if not preq[child]:
                    nopreq.append(child)
            count=count+1
        return numCourses==count        

1. The code builds a map:

• courses: Tracks course’s child for a course.
• preq: Tracks prerequisites for courses.

2. It starts with courses with no prerequisites.

3. It then iterates:

• Pick a course without prereqs.
• Mark it as completed (remove from processing list).
• Check courses dependent on the completed one.
• If all its prerequisites are done, add it to the processing list for the next round.

4. If all courses can be completed this way (processed), it means there’s a valid order to take all courses respecting prerequisites (topological sort).