-
Notifications
You must be signed in to change notification settings - Fork 1
/
1462+Course Schedule IV.cpp
37 lines (30 loc) · 1.21 KB
/
1462+Course Schedule IV.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
public:
vector<bool> checkIfPrerequisite(int numCourses, vector<vector<int>>& prerequisites, vector<vector<int>>& queries) {
// 先修课程,grpah[i][j] = 1 表示 i 是 j 的先修课程
bool graph[numCourses][numCourses];
memset(graph, 0, sizeof(bool)*numCourses*numCourses);
// 构建图
for (const auto &data : prerequisites) {
graph[data[0]][data[1]] = true;
}
// Floyd算法的本质是DP,而k是DP的阶段,因此要写最外面
for (int k = 0; k < numCourses; ++k) {
for (int i = 0; i < numCourses; ++i) {
for (int j = 0; j < numCourses; ++j) {
// i 是 k 的先导课程,k 是 j 的先导课程
if (graph[i][k] && graph[k][j]) {
graph[i][j] = true;
}
}
}
}
// 遍历quries直接从graph得到结果
vector<bool> res;
for (const auto &q : queries) {
if (graph[q[0]][q[1]]) res.push_back(true);
else res.push_back(false);
}
return res;
}
};