LeetCode #1462 Medium

Course Schedule IV

Answer whether one course is a direct or indirect prerequisite of another.

graphtransitive-closuretopological-sort

02

Intuition

Running a fresh graph search for every query repeats the same reachability work. The prerequisite graph is a DAG, so each course's complete prerequisite set can be propagated in topological order. When a course becomes ready, all information from its predecessors is already known. Unioning those sets with the direct predecessor answers every later query in constant average lookup time.

How to spot this pattern

Many reachability queries over one fixed DAG justify precomputing transitive closure. Topological propagation is especially natural when each node's answer can be assembled from its predecessors' answers.

03

Approach

1

Orient edges from prerequisite to dependent course

For pair [a, b], add a -> b and increase b's indegree. Maintain a set for every course that will contain all courses required before it.

2

Propagate prerequisite ancestry topologically

Start with zero-indegree courses. For every edge course -> next, add course and everything required by course into next's set before decreasing its indegree.

3

Answer from the completed closure

After all courses are processed, query [u, v] is true exactly when u belongs to the prerequisite set of v. This includes paths of any positive length but never treats a course as its own prerequisite.

04

Solution

▶1class Solution:
▶2    def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:
▶3        graph = [[] for _ in range(numCourses)]
▶4        indegree = [0] * numCourses
▶5        required = [set() for _ in range(numCourses)]
▶6        for prerequisite, course in prerequisites:
▶7            graph[prerequisite].append(course)
▶8            indegree[course] += 1
▶9 
▶10        queue = deque(course for course in range(numCourses) if indegree[course] == 0)
▶11        while queue:
▶12            course = queue.popleft()
▶13            for next_course in graph[course]:
▶14                required[next_course].update(required[course])
▶15                required[next_course].add(course)
▶16                indegree[next_course] -= 1
▶17                if indegree[next_course] == 0:
▶18                    queue.append(next_course)
▶19 
▶20        return [prerequisite in required[course] for prerequisite, course in queries]

05

Common pitfalls

Reversing the prerequisite edge

✗ Wrong

graph[b].append(a)

✓ Right

graph[a].append(b)

The pair states that course a must come before course b.

Propagating ancestors but omitting the direct course

✗ Wrong

required[next].update(required[course])

✓ Right

required[next].update(required[course])
required[next].add(course)

The direct predecessor is a prerequisite even if it has no ancestors.

Checking the wrong set

✗ Wrong

v in required[u]

✓ Right

u in required[v]

The set belongs to the dependent course and contains what must precede it.

06

Edge cases

A direct prerequisite

The predecessor itself is inserted into the dependent course's set.

A multi-course chain

Set propagation carries every earlier ancestor through the chain.

Unrelated courses

No propagation connects their sets, so the query is false.

07

Complexity

Time

O(EV + Q)

Space

O(E + V^2)

In the worst case each prerequisite set contains most courses.