域名注册好如何网站建设,临潼区做网站的公司,网站开发师培训,腾讯企点收费标准2023-03-29每日一题
一、题目编号
1462. 课程表 IV二、题目链接
点击跳转到题目位置
三、题目描述
你总共需要上 numCourses 门课#xff0c;课程编号依次为 0 到 numCourses-1 。你会得到一个数组 prerequisite #xff0c;其中 prerequisites[i] [ai, bi] 表示如果你…2023-03-29每日一题
一、题目编号
1462. 课程表 IV二、题目链接
点击跳转到题目位置
三、题目描述
你总共需要上 numCourses 门课课程编号依次为 0 到 numCourses-1 。你会得到一个数组 prerequisite 其中 prerequisites[i] [ai, bi] 表示如果你想选 bi 课程你 必须 先选 ai 课程。
有的课会有直接的先修课程比如如果想上课程 1 你必须先上课程 0 那么会以 [0,1] 数对的形式给出先修课程数对。 先决条件也可以是 间接 的。如果课程 a 是课程 b 的先决条件课程 b 是课程 c 的先决条件那么课程 a 就是课程 c 的先决条件。
你也得到一个数组 queries 其中 queries[j] [uj, vj]。对于第 j 个查询您应该回答课程 uj 是否是课程 vj 的先决条件。
返回一个布尔数组 answer 其中 answer[j] 是第 j 个查询的答案。
示例 1 示例 2
示例 3 提示
2 numCourses 1000 prerequisites.length (numCourses * (numCourses - 1) / 2)prerequisites[i].length 20 ai, bi n - 1ai ! bi每一对 [ai, bi] 都 不同先修课程图中没有环。1 queries.length 1040 ui, vi n - 1ui ! vi
四、解题代码
在这里插入代码片class Solution {
public:vectorbool checkIfPrerequisite(int numCourses, vectorvectorint prerequisites, vectorvectorint queries) {vectorvectorint g(numCourses);vectorint indgree(numCourses, 0);vectorvectorbool isPre(numCourses, vectorbool(numCourses, false));for (auto p : prerequisites) {indgree[p[1]];g[p[0]].push_back(p[1]);}queueint q;for (int i 0; i numCourses; i) {if (indgree[i] 0) {q.push(i);}}while (!q.empty()) {auto cur q.front();q.pop();for (auto ne : g[cur]) {isPre[cur][ne] true;for (int i 0; i numCourses; i) {isPre[i][ne] isPre[i][ne] | isPre[i][cur];}--indgree[ne];if (indgree[ne] 0) {q.push(ne);}}}vectorbool res;for (auto query : queries) {res.push_back(isPre[query[0]][query[1]]);}return res;}
};五、解题思路
(1) 使用广度优先搜索拓扑排序
