题解 | 课程表IV
题干分析：
题设给予我们课程个数，一个二维数组标识某门课程是另一门课程的直接前置课程，同时给予我们需要进行判定是否为前置课程（包括直接与间接前置）的课程组，要求我们返回这些课程组的判定结果。
算法思路：
通过题设给予的信息构建邻接矩阵，然后使用Warshall算法求出可达性矩阵。此后我们根据需要查询的课程对，在此可达性矩阵中直接查询结果即可。
实现代码：
vector<bool> checkIfPrerequisite(
int numCourses,
vector<vector<int> > &prerequisites,
vector<vector<int> > &queries
) {
vector adj(numCourses, vector(numCourses, false));
for (auto &link: prerequisites) adj[link[0]][link[1]] = true;
// Warshall
for (int k = 0; k < numCourses; ++k) {
for (int i = 0; i < numCourses; ++i) {
if (adj[i][k]) {
for (int j = 0; j < numCourses; ++j) {
if (adj[k][j]) adj[i][j] = true;
}
}
}
}
const int n = static_cast<int>(queries.size());
vector ans(n, false);
for (int i = 0; i < n; ++i) ans[i] = adj[queries[i][0]][queries[i][1]];
return ans;
}
复杂度分析：
- 时间复杂度：Warshall算法时间复杂度为O（n^3）占主体，总时间复杂度为O（n^3）
- 空间复杂度：邻接矩阵和可达性矩阵使用同一片O（n^2）空间，空间复杂度总计为O(n^2)
叮咚买菜工作强度 208人发布