1462. Course Schedule IV

Depth-First Search Breadth-First Search Graph Topological Sort

Time: O(n³)

Space: O(n²)

Intuition

Transitive closure: b is a prerequisite of a if there exists a path b->a. Precompute reachability using BFS/DFS from each node.

Algorithm

1BFS/DFS from each course, mark all reachable courses.
2For each query (u,v): check if u is reachable from v.

Common Pitfalls

•The graph is a DAG. For each query, answer is whether there is a directed path from prerequisites to the course.

1462.cs

// Approach: Floyd-Warshall transitive closure; isPrerequisite[i][j] = true if i can reach j through the prerequisite graph.
// Time: O(n³) Space: O(n²)

public class Solution
{
    public IList<bool> CheckIfPrerequisite(int numCourses, int[][] prerequisites, int[][] queries)
    {
        List<bool> ans = new List<bool>();
        // isPrerequisite[i][j] := true if course i is a prerequisite of course j
        bool[,] isPrerequisite = new bool[numCourses, numCourses];

        foreach (var prerequisite in prerequisites)
        {
            int u = prerequisite[0];
            int v = prerequisite[1];
            isPrerequisite[u, v] = true;
        }

        for (int k = 0; k < numCourses; ++k)
        {
            for (int i = 0; i < numCourses; ++i)
            {
                for (int j = 0; j < numCourses; ++j)
                    isPrerequisite[i, j] = isPrerequisite[i, j] || (isPrerequisite[i, k] && isPrerequisite[k, j]);
            }
        }

        foreach (var query in queries)
        {
            int u = query[0];
            int v = query[1];
            ans.Add(isPrerequisite[u, v]);
        }

        return ans;
    }
}

Was this solution helpful?