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] = [ai, bi]
indicates that you must take course ai
first if you want to take course bi
.
[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] = [uj, vj]
. For the jth
query, you should answer whether course uj
is a prerequisite of course vj
or not.
Return a boolean array answer
, where answer[j]
is the answer to the jth
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 <= ai, bi <= n - 1
ai != bi
[ai, bi]
are unique.1 <= queries.length <= 104
0 <= ui, vi <= n - 1
ui != vi
import java.util.LinkedList
import java.util.Queue
class Solution {
fun checkIfPrerequisite(
numCourses: Int,
prerequisites: Array<IntArray>,
queries: Array<IntArray>,
): List<Boolean> {
val m: MutableMap<Int, MutableList<Int>> = HashMap()
val ind = IntArray(numCourses)
for (p in prerequisites) {
m.computeIfAbsent(p[1]) { _: Int? -> ArrayList() }.add(p[0])
ind[p[0]]++
}
val r = Array(numCourses) { BooleanArray(numCourses) }
val q: Queue<Int> = LinkedList()
for (i in 0 until numCourses) {
if (ind[i] == 0) {
q.add(i)
}
}
while (q.isNotEmpty()) {
val j = q.poll()
for (k in m.getOrDefault(j, ArrayList<Int>())) {
r[k][j] = true
for (l in r.indices) {
if (r[j][l]) {
r[k][l] = true
}
}
ind[k]--
if (ind[k] == 0) {
q.offer(k)
}
}
}
val a: MutableList<Boolean> = ArrayList()
for (qr in queries) {
a.add(r[qr[0]][qr[1]])
}
return a
}
}