Tag

【拓扑排序】【传递闭包】【并查集】【数组】

---

题目来源

1462. 课程表 IV

---

题目解读

给你一个表示课程先决条件的数组 prerequisites，prerequisites[i] = [a, b] 表示在学习课程 b 之前要先学习课程 a，课程 a 是 b 的直接先决条件。如果课程 a 是课程 b 的先决条件，课程 b 是课程 c 的先决条件，那么课程 a 是课程 c 的间接先决条件。现在需要你根据查询数组 queries，根据 queries[i] = [u, v] 查询课程 u 是否是课程 v 的先决条件，最后返回一个 bool 类型的数组 ret，ret[i] 表示数组 queries 的第 i 次查询的结果。

---

解题思路

主要思路是怎么建立课程节点之间的联系。以下介绍两种方法。

方法一：Floyd传递闭包

一个直观的想法是利用提供的 prerequisites 数组现将两个课程节点连接起来，根据 $Floyd$ 算法传递闭包，建立课程节点之间的联系。

实现代码

class Solution {
public:vector<bool> checkIfPrerequisite(int numCourses, vector<vector<int>>& prerequisites, vector<vector<int>>& queries) {vector<vector<bool>> graphy(numCourses, vector<bool>(numCourses, false));for (auto pre : prerequisites) {int x = pre[0], y = pre[1];graphy[x][y] = true;}for (int k = 0; k < numCourses; ++k) {             // 中间节点for (int i = 0; i < numCourses; ++i) {for (int j = 0; j < numCourses; ++j) {if (graphy[i][k] && graphy[k][j]) {graphy[i][j] = true;}}}}vector<bool> res;for (auto query : queries) {int x = query[0], y = query[1];res.push_back(graphy[x][y]);} return res;}
};

复杂度分析

时间复杂度：$O(numCourse{s}^3)$，$numCourses$ 表示课程的数目，本题数据量为 $10^2$，因此不会超时。

空间复杂度：$O(numCourse{s}^2)$，主要是建图占用的额外空间。

方法二：拓扑排序

题目中保证没有环，可以利用拓扑排序来建立课程节点之间的联系，通过拓扑排序记录每个课程节点的直接或间接先决条件。

具体地，维护一个数组 inDegree 用来记录课程节点的入度；维护一个队列 que 存放拓扑排序的课程节点，初始化加入入度为 0 的课程节点；维护一个 edges 用来记录课程节点之间的关系；维护一个 numCourse x numCourse 的矩阵 isPre，其中 isPre[x][y] 表示课程 x 是否是课程 y 的直接或者间接先决条件。

程序执行流程，前面就是拓扑排序的常规操作，包括：

• 记录课程节点的入度；
• 建立课程节点之间的边关系；
• 将入度为 0 的节点加入队列中；
• 依次取出队列中入度为 0 的课程节点，设当前出队的节点为 x，枚举 edges[x] 中的课程节点 y，对其进行 操作，并 --inDegree[y]，如果 inDegree[y] = 0，则加入队列。

以上是拓扑排序的模板操作，现在来介绍一下其中的 操作。

当前出队的节点为 x，枚举 edges[x] 中的课程节点 y，于是课程节点 x 为 y 的直接先决条件，因此 isPre[x][y] = true，这时候枚举其他的课程节点 i，更新 isPre[i][y] = isPre[i][y] | isPre[i][x]。

最后，遍历查询数组的每一个查询，根据 isPre 结果即可得到每一个查询结果。

实现代码

class Solution {
public:vector<bool> checkIfPrerequisite(int numCourses, vector<vector<int>>& prerequisites, vector<vector<int>>& queries) {vector<int> inDegree(numCourses);queue<int> que;vector<vector<int>> edges(numCourses);vector<vector<bool>> isPre(numCourses, vector<bool>(numCourses, false));for (auto pre : prerequisites) {int x = pre[0], y = pre[1];++inDegree[y];edges[x].push_back(y);}for (int i = 0; i < numCourses; ++i) {if (inDegree[i] == 0) {que.push(i);}}while (!que.empty()) {int x = que.front();que.pop();for (auto y : edges[x]) {isPre[x][y] = true;for (int i = 0; i < numCourses; ++i) {isPre[i][y] = isPre[i][y] | isPre[i][x];}--inDegree[y];if (inDegree[y] == 0) {que.push(y);}}}vector<bool> res;for (auto query : queries) {int x = query[0], y = query[1];if  (isPre[x][y]) {res.push_back(true);}else res.push_back(false);} return res;}
};/*
拓扑排序
题目中保证没有环，可以利用拓扑排序来建立课程节点之间的联系
通过拓扑排序记录每个课程节点的直接或间接先决条件
*/ 

复杂度分析

时间复杂度：$O(numCours{e}^2+n+m)$，其中 $numCourses$ 是课程数，$n$ 为数组 prerequisites 的长度，$m$ 为查询数。主要是计算 isPre 矩阵的时间复杂度为 $O(numCOurs{e}^2)$，构建有向图复杂度为 $O(numCourses+n)$，$m$ 次查询时间复杂度为 $O(m)$。

空间复杂度：$O(numCourse{s}^2+n)$，主要是构建有向图和矩阵 isPre 的空间开销。

思考

题目中的课程节点之间的先决关系类似于一种父子关系，能否利用【并查集】的方法解决该问题呢？

写在最后

如果文章内容有任何错误或者您对文章有任何疑问，欢迎私信博主或者在评论区指出 💬💬💬。

如果大家有更优的时间、空间复杂度方法，欢迎评论区交流。

最后，感谢您的阅读，如果感到有所收获的话可以给博主点一个 👍 哦。