Description Link to heading

1462. Course Schedule IV (Medium)

There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [aᵢ, bᵢ] indicates that you must take course aᵢ first if you want to take course bᵢ.

  • For example, the pair [0, 1] indicates that you have to take course 0 before you can take course 1.

Prerequisites can also be indirect. If course a is a prerequisite of course b, and course b is a prerequisite of course c, then course a is a prerequisite of course c.

You are also given an array queries where queries[j] = [uⱼ, vⱼ]. For the jᵗʰ query, you should answer whether course uⱼ is a prerequisite of course vⱼ or not.

Return a boolean array answer , where answer[j] is the answer to the jᵗʰ query.

Example 1:

Input: numCourses = 2, prerequisites = [[1,0]], queries = [[0,1],[1,0]]
Output: [false,true]
Explanation: The pair [1, 0] indicates that you have to take course 1 before you can take course 0.
Course 0 is not a prerequisite of course 1, but the opposite is true.

Example 2:

Input: numCourses = 2, prerequisites = [], queries = [[1,0],[0,1]]
Output: [false,false]
Explanation: There are no prerequisites, and each course is independent.

Example 3:

Input: numCourses = 3, prerequisites = [[1,2],[1,0],[2,0]], queries = [[1,0],[1,2]]
Output: [true,true]

Constraints:

  • 2 <= numCourses <= 100
  • 0 <= prerequisites.length <= (numCourses * (numCourses - 1) / 2)
  • prerequisites[i].length == 2
  • 0 <= aᵢ, bᵢ <= n - 1
  • aᵢ != bᵢ
  • All the pairs [aᵢ, bᵢ] are unique.
  • The prerequisites graph has no cycles.
  • 1 <= queries.length <= 10⁴
  • 0 <= uᵢ, vᵢ <= n - 1
  • uᵢ != vᵢ

Solution Link to heading

We must still incorporate topological sorting into the solution. During the process of topological sorting, we also need to traverse all the courses. If the course being traversed is a prerequisite for cur, it will certainly be a prerequisite for next as well.

Code Link to heading 

class Solution {
  public:
    vector<bool> checkIfPrerequisite(int numCourses, vector<vector<int>> &prerequisites, vector<vector<int>> &queries) {
        vector<vector<int>> ispre(numCourses, vector<int>(numCourses, 0));
        vector<vector<int>> graph(numCourses);
        vector<int> indeg(numCourses);
        for (auto &vec : prerequisites) {
            int x = vec[0], y = vec[1];
            graph[x].push_back(y);
            ++indeg[y];
        }
        queue<int> q;
        for (int i = 0; i < numCourses; ++i) {
            if (indeg[i] == 0) {
                q.push(i);
            }
        }
        while (!q.empty()) {
            auto cur = q.front();
            q.pop();
            for (int next : graph[cur]) {
                ispre[cur][next] = 1;
                for (int i = 0; i < numCourses; ++i) {
                    if (ispre[i][cur] == 1) {
                        ispre[i][next] = 1;
                    }
                }
                if (--indeg[next] == 0) {
                    q.push(next);
                }
            }
        }
        vector<bool> ans;
        ans.reserve(queries.size());
        for (auto &qry : queries) {
            ans.push_back(ispre[qry[0]][qry[1]] == 1);
        }
        return ans;
    }
};