1462. 课程表 IV - Kotlin 拓扑排序 BFS 分治

Problem: 1462. 课程表 IV

思路

基于分治的思想，对于任意一个课程，它的先决条件课程必然等于它的所有直接前置课程的先决条件课程的交集（即所有间接前置课程），加上它的所有直接前置课程，我们只需要在进行拓扑排序的过程中通过一个数据结构记录下结果即可

设prerequisiteMap[a]为一个HashSet<Int>，prerequisiteMap[a].contains(b)指课程b是课程a的先决条件（这里的顺序和题目是相反的，是因为这样的话可以更方便地基于课程的先决条件集合进行取交集操作）

正常写出基于BFS的拓扑排序：若课程a是课程b的先决条件，则课程a有一条指向课程b的边，记录下每个节点的入度值和出度节点，以入度为0的点起始，从图中去除该点，并令该点的所有出度节点的入度值-1，当有节点入度值为0时则加入队列

当我们遍历节点a的任意一个出度节点b时，b的先决条件课程等于b当前的先决条件课程和a的先决条件课程和a三者的交集，即：

prerequisiteMap[b].addAll(prerequisiteMap[a])
prerequisiteMap[b].add(a)

最后遍历queries，当prerequisiteMap[query[1]].contains(query[0])时结果为true，反之则为false

复杂度

• 时间复杂度:

• 空间复杂度:

Code

class Solution
fun Solution.checkIfPrerequisite(
    numCourses: Int,
    prerequisites: Array<IntArray>,
    queries: Array<IntArray>
): List<Boolean> {
    val queue = ArrayDeque<Int>()
    val prerequisiteMap = Array(numCourses) { HashSet<Int>() }
    val inDegree = IntArray(numCourses)
    val outDegree = Array<ArrayList<Int>>(numCourses) { ArrayList() }
    val ans = ArrayList<Boolean>()

    for (pair in prerequisites) {
        inDegree[pair[1]]++
        outDegree[pair[0]].add(pair[1])
    }

    inDegree.forEachIndexed() { index, value -> if (value == 0) queue.addLast(index) }

    while (queue.isNotEmpty()) {
        val course = queue.removeFirst()
        for (unlockedCourse in outDegree[course]) {
            prerequisiteMap[unlockedCourse].addAll(prerequisiteMap[course])
            prerequisiteMap[unlockedCourse].add(course)
            if (--inDegree[unlockedCourse] == 0) {
                queue.add(unlockedCourse)
            }
        }
    }

    queries.forEach { query -> ans.add(prerequisiteMap[query[1]].contains(query[0])) }

    return ans
}