1462

1462. Course Schedule IV (Medium)

There are a total of n courses you have to take, labeled from 0 to n-1.

Some courses may have direct prerequisites, for example, to take course 0 you have first to take course 1, which is expressed as a pair: [1,0]

Given the total number of courses n, a list of direct prerequisite pairs and a list of queries pairs.

You should answer for each queries[i] whether the course queries[i][0] is a prerequisite of the course queries[i][1] or not.

Return a list of boolean, the answers to the given queries.

Please note that 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.

 

Example 1:

Input: n = 2, prerequisites = [[1,0]], queries = [[0,1],[1,0]]
Output: [false,true]
Explanation: course 0 is not a prerequisite of course 1 but the opposite is true.

Example 2:

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

Example 3:

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

Example 4:

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

Example 5:

Input: n = 5, prerequisites = [[0,1],[1,2],[2,3],[3,4]], queries = [[0,4],[4,0],[1,3],[3,0]]
Output: [true,false,true,false]

 

Constraints:

• 2 <= n <= 100
• 0 <= prerequisite.length <= (n * (n - 1) / 2)
• 0 <= prerequisite[i][0], prerequisite[i][1] < n
• prerequisite[i][0] != prerequisite[i][1]
• The prerequisites graph has no cycles.
• The prerequisites graph has no repeated edges.
• 1 <= queries.length <= 10^4
• queries[i][0] != queries[i][1]

Related Topics:
Graph

Solution 1. DFS

We can first build a directed graph given the prerequisite. Then for each query, we DFS to check we can reach q[1] from q[0]. To save computation, we can memoize the result of any from, to node pairs we've seen along the DFS process.

// OJ: https://leetcode.com/problems/course-schedule-iv/
// Author: github.com/lzl124631x
// Time: O(min(N^2, Q))
// Space: O(N^2)
class Solution {
    vector<vector<int>> G, m;
    bool dfs(int from, int to) {
        if (m[from][to] != -1) return m[from][to];
        for (int v : G[from]) {
            if (dfs(v, to)) return m[from][to] = 1;
        }
        return m[from][to] = 0;
    }
public:
    vector<bool> checkIfPrerequisite(int N, vector<vector<int>>& E, vector<vector<int>>& Q) {
        G.assign(N, {});
        m.assign(N, vector<int>(N, -1));
        for (int i = 0; i < N; ++i) m[i][i] = 1;
        for (auto &e : E) G[e[0]].push_back(e[1]);
        vector<bool> ans;
        for (auto &q : Q) ans.push_back(dfs(q[0], q[1]));
        return ans;
    }
};

Solution 2. Floyd-Warshall

We can use the Floyd-Warshall algorithm to fine all the shortest paths of any node pairs in a weighted graph. Here we can make simple adjustment to it to just store whether any node pairs are reachable.

// OJ: https://leetcode.com/problems/course-schedule-iv/
// Author: github.com/lzl124631x
// Time: O(N^3 + Q)
// Space: O(N^2)
class Solution {
public:
    vector<bool> checkIfPrerequisite(int N, vector<vector<int>>& E, vector<vector<int>>& Q) {
        vector<vector<bool>> m(N, vector<bool>(N));
        for (auto &e : E) m[e[0]][e[1]] = true;
        for (int i = 0; i < N; ++i) {
            for (int u = 0; u < N; ++u) {
                for (int v = 0; v < N; ++v) {
                    m[u][v] = m[u][v] || (m[u][i] && m[i][v]);
                }
            }
        }
        vector<bool> ans;
        for (auto &q : Q) ans.push_back(m[q[0]][q[1]]);
        return ans;
    }
};

Solution 3. Topological Sort

// OJ: https://leetcode.com/problems/course-schedule-iv/
// Author: github.com/lzl124631x
// Time: O(N^2 + Q)
// Space: O(N^2)
class Solution {
public:
    vector<bool> checkIfPrerequisite(int N, vector<vector<int>>& P, vector<vector<int>>& Q) {
        vector<vector<int>> G(N);
        vector<int> indegree(N), seen(N);
        vector<unordered_set<int>> pre(N);
        for (auto &p : P) {
            int u = p[0], v = p[1];
            G[u].push_back(v);
            indegree[v]++;
        }
        queue<int> q;
        for (int i = 0; i < N; ++i) {
            if (indegree[i] == 0) q.push(i);
        }
        while (q.size()) {
            int u = q.front();
            q.pop();
            for (int v : G[u]) {
                for (int p : pre[u]) {
                    pre[v].insert(p);
                }
                pre[v].insert(u);
                if (--indegree[v] == 0) {
                    q.push(v);
                }
            }
        }
        vector<bool> ans;
        for (auto q : Q) {
            ans.push_back(pre[q[1]].count(q[0]));
        }
        return ans;
    }
};