福州最好的网站建设服务商,广告设计软件免费下载,自助建站系统网站建设开发,网站集约化建设进度报告文章目录 Tag题目来源题目解读解题思路方法一#xff1a;Floyd传递闭包方法二#xff1a;拓扑排序 思考写在最后 Tag
【拓扑排序】【传递闭包】【并查集】【数组】 题目来源
1462. 课程表 IV 题目解读
给你一个表示课程先决条件的数组 prerequisites#xff0c;prerequis… 文章目录 Tag题目来源题目解读解题思路方法一Floyd传递闭包方法二拓扑排序 思考写在最后 Tag
【拓扑排序】【传递闭包】【并查集】【数组】 题目来源
1462. 课程表 IV 题目解读
给你一个表示课程先决条件的数组 prerequisitesprerequisites[i] [a, b] 表示在学习课程 b 之前要先学习课程 a课程 a 是 b 的直接先决条件。如果课程 a 是课程 b 的先决条件课程 b 是课程 c 的先决条件那么课程 a 是课程 c 的间接先决条件。现在需要你根据查询数组 queries根据 queries[i] [u, v] 查询课程 u 是否是课程 v 的先决条件最后返回一个 bool 类型的数组 retret[i] 表示数组 queries 的第 i 次查询的结果。 解题思路
主要思路是怎么建立课程节点之间的联系。以下介绍两种方法。
方法一Floyd传递闭包
一个直观的想法是利用提供的 prerequisites 数组现将两个课程节点连接起来根据 F l o y d Floyd Floyd 算法传递闭包建立课程节点之间的联系。
实现代码
class Solution {
public:vectorbool checkIfPrerequisite(int numCourses, vectorvectorint prerequisites, vectorvectorint queries) {vectorvectorbool graphy(numCourses, vectorbool(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;}}}}vectorbool res;for (auto query : queries) {int x query[0], y query[1];res.push_back(graphy[x][y]);} return res;}
};复杂度分析
时间复杂度 O ( n u m C o u r s e s 3 ) O(numCourses^3) O(numCourses3) n u m C o u r s e s numCourses numCourses 表示课程的数目本题数据量为 1 0 2 10^2 102因此不会超时。
空间复杂度 O ( n u m C o u r s e s 2 ) O(numCourses^2) O(numCourses2)主要是建图占用的额外空间。
方法二拓扑排序
题目中保证没有环可以利用拓扑排序来建立课程节点之间的联系通过拓扑排序记录每个课程节点的直接或间接先决条件。
具体地维护一个数组 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:vectorbool checkIfPrerequisite(int numCourses, vectorvectorint prerequisites, vectorvectorint queries) {vectorint inDegree(numCourses);queueint que;vectorvectorint edges(numCourses);vectorvectorbool isPre(numCourses, vectorbool(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);}}}vectorbool 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 ( n u m C o u r s e 2 n m ) O(numCourse^2nm) O(numCourse2nm)其中 n u m C o u r s e s numCourses numCourses 是课程数 n n n 为数组 prerequisites 的长度 m m m 为查询数。主要是计算 isPre 矩阵的时间复杂度为 O ( n u m C O u r s e 2 ) O(numCOurse^2) O(numCOurse2)构建有向图复杂度为 O ( n u m C o u r s e s n ) O(numCoursesn) O(numCoursesn) m m m 次查询时间复杂度为 O ( m ) O(m) O(m)。
空间复杂度 O ( n u m C o u r s e s 2 n ) O(numCourses^2n) O(numCourses2n)主要是构建有向图和矩阵 isPre 的空间开销。
思考
题目中的课程节点之间的先决关系类似于一种父子关系能否利用【并查集】的方法解决该问题呢
写在最后
如果文章内容有任何错误或者您对文章有任何疑问欢迎私信博主或者在评论区指出 。
如果大家有更优的时间、空间复杂度方法欢迎评论区交流。
最后感谢您的阅读如果感到有所收获的话可以给博主点一个 哦。
