Formatted question description: https://leetcode.ca/all/1462.html
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/
// Time: O(V + E)
// Space: O(V^2)
class Solution {
vector<vector<int>> G, m;
bool dfs(int from, int to) {
if (m[from][to] != -1) return m[from][to];
bool ans = false;
for (int v : G[from]) {
if (dfs(v, to)) {
ans = true;
break;
}
}
return m[from][to] = ans;
}
public:
vector<bool> checkIfPrerequisite(int n, vector<vector<int>>& A, 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 : A) G[e[0]].push_back(e[1]);
vector<bool> ans;
for (auto &e : Q) ans.push_back(dfs(e[0], e[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/
// Time: O(V^3)
// Space: O(V^2)
class Solution {
public:
vector<bool> checkIfPrerequisite(int n, vector<vector<int>>& A, vector<vector<int>>& Q) {
vector<vector<bool>> m(n, vector<bool>(n));
for (auto &e : A) 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;
}
};
Java
class Solution {
public List<Boolean> checkIfPrerequisite(int n, int[][] prerequisites, int[][] queries) {
Map<Integer, Set<Integer>> prerequisiteMap = new HashMap<Integer, Set<Integer>>();
for (int[] prerequisite : prerequisites) {
int course0 = prerequisite[0], course1 = prerequisite[1];
Set<Integer> set = prerequisiteMap.getOrDefault(course0, new HashSet<Integer>());
set.add(course1);
prerequisiteMap.put(course0, set);
}
List<Boolean> checkList = new ArrayList<Boolean>();
Map<Integer, Boolean> queryMap = new HashMap<Integer, Boolean>();
int queriesCount = queries.length;
for (int i = 0; i < queriesCount; i++) {
int[] query = queries[i];
boolean isPrerequisite = search(prerequisiteMap, queryMap, query[0], query[1], n);
checkList.add(isPrerequisite);
}
return checkList;
}
public boolean search(Map<Integer, Set<Integer>> prerequisiteMap, Map<Integer, Boolean> queryMap, int course0, int course1, int n) {
int key = course0 * n + course1;
if (queryMap.containsKey(key))
return queryMap.get(key);
Set<Integer> set = prerequisiteMap.getOrDefault(course0, new HashSet<Integer>());
if (set.contains(course1)) {
queryMap.put(key, true);
return true;
} else {
for (int nextCourse : set) {
if (search(prerequisiteMap, queryMap, nextCourse, course1, n)) {
queryMap.put(key, true);
return true;
}
}
}
queryMap.put(key, false);
return false;
}
}