Problem of The Day: Course Schedule IV

Problem Statement

BFS Approach [Accepted]

class Solution:
    def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:
        graph = {i: [] for i in range(numCourses)}
        indegree = {i: 0 for i in range(numCourses)}
        for src, des in prerequisites:
            graph[src].append(des)

        def isReachable(u, v, visited):
            q = deque()
            q.append(u)
            while q:
                node = q.popleft()
                if node == v:
                    return True
                visited.add(node)
                for nei in graph[node]:
                    if nei not in visited:
                        q.append(nei)
            return False

        res = []
        for u, v in queries:
            if isReachable(u, v, set()):
                res.append(True)
            else:
                res.append(False)
        return res

Optimized Approach: Precompute Reachability with Floyd-Warshall or DFS

from collections import defaultdict, deque

class Solution:
    def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:
        # Precompute reachability using a transitive closure
        reachable = [[False] * numCourses for _ in range(numCourses)]

        # Build adjacency list
        graph = defaultdict(list)
        for src, des in prerequisites:
            graph[src].append(des)

        # Use DFS to find all reachable nodes for each course
        def dfs(course, start):
            for neighbor in graph[course]:
                if not reachable[start][neighbor]:
                    reachable[start][neighbor] = True
                    dfs(neighbor, start)

        # Precompute reachability for each course
        for course in range(numCourses):
            dfs(course, course)

        # Answer queries using precomputed reachability
        return [reachable[u][v] for u, v in queries]

• time: O(V(V+E)+Q) where Q is the number of queries, V is vertices and E is edges.
• space: O(V^2 + (V + E))

Editorial

Approach 3: Topological Sort - Kahn’s Algorithm

class Solution:
    def checkIfPrerequisite(
        self,
        numCourses: int,
        prerequisites: List[List[int]],
        queries: List[List[int]],
    ) -> List[bool]:
        adjList = defaultdict(list)
        indegree = [0] * numCourses

        for edge in prerequisites:
            adjList[edge[0]].append(edge[1])
            indegree[edge[1]] += 1

        q = deque()
        for i in range(numCourses):
            if indegree[i] == 0:
                q.append(i)

        nodePrerequisites = defaultdict(set)

        while q:
            node = q.popleft()

            for adj in adjList[node]:
                # Add node and prerequisite of the node to the prerequisites of adj
                nodePrerequisites[adj].add(node)
                for prereq in nodePrerequisites[node]:
                    nodePrerequisites[adj].add(prereq)

                indegree[adj] -= 1
                if indegree[adj] == 0:
                    q.append(adj)

        answer = []
        for q in queries:
            answer.append(q[0] in nodePrerequisites[q[1]])

        return answer

Approach 4: Floyd Warshall Algorithm

class Solution:
    def checkIfPrerequisite(
        self,
        numCourses: int,
        prerequisites: List[List[int]],
        queries: List[List[int]],
    ) -> List[bool]:
        isPrerequisite = [[False] * numCourses for _ in range(numCourses)]

        for edge in prerequisites:
            isPrerequisite[edge[0]][edge[1]] = True

        for intermediate in range(numCourses):
            for src in range(numCourses):
                for target in range(numCourses):
                    # If there is a path src -> intermediate and intermediate -> target, then src -> target exists as well
                    isPrerequisite[src][target] = isPrerequisite[src][
                        target
                    ] or (
                        isPrerequisite[src][intermediate]
                        and isPrerequisite[intermediate][target]
                    )

        answer = []
        for query in queries:
            answer.append(isPrerequisite[query[0]][query[1]])

        return answer