_1462. Course Schedule IV.md

1462. Course Schedule IV

All prompts are owned by LeetCode. To view the prompt, click the title link above.

Back to top

---

First completed : January 27, 2025

Last updated : January 27, 2025

---

Related Topics : Depth-First Search, Breadth-First Search, Graph, Topological Sort

Acceptance Rate : 59.6 %

---

The only difference between the two is that in V1, I followed the prereq chains as they were queried. I realized that it just made more sense to precompute everything and essentially have a set of ALL prereqs for each course just since the number of queries was approaching such a high number.

---

Solutions

• m1462 v2 precomputing.py
• m1462.py

Python

m1462 v2 precomputing.py

class Solution:
    def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:
        prereqs = defaultdict(set)

        for a, b in prerequisites :
            prereqs[b].add(a)

        for k in range(numCourses) :
            to_visit = prereqs[k].copy()
            visited = set()
            while to_visit :
                curr = to_visit.pop()
                if curr in visited :
                    continue
                visited.add(curr)
                prereqs[k].add(curr)
                for nxt in prereqs[curr] :
                    if nxt not in visited :
                        to_visit.add(nxt)

        return [a in prereqs[b] for a, b in queries]

m1462.py

class Solution:
    def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:
        prereqs = defaultdict(set)

        for a, b in prerequisites :
            prereqs[b].add(a)

        output = []

        for i, (a, b) in enumerate(queries) :
            to_visit = [b]
            visited = set()

            while to_visit :
                x = to_visit.pop()
                if x in visited :
                    continue
                visited.add(x)

                if x == a :
                    output.append(True)
                    break

                for y in prereqs[x] :
                    if y not in visited :
                        to_visit.append(y)

            if len(output) <= i :
                output.append(False)

        return output