C ++中的课程表IV
假设我们总共可以选n门课程，这些课程从0标记为n-1。
有些课程可能有直接的先决条件，例如，要选修课程0，我们首先要选修课程1，该课程以一对表示：[1,0]。
因此，如果我们有多个课程n，则有一个直接的先决条件对列表和一个查询对列表。
无论课程查询[i][0]是否是课程查询[i][1]的前提条件，您都应该找到答案。最后，我们必须返回布尔值列表，即给定查询的答案。
我们必须记住，如果课程a是课程b的前提，而课程b是课程c的前提，那么课程a是课程c的前提。
因此，如果输入像n=3，先决条件=[[1,2,,[1,0]，[2,0]]，查询=[[1,0]，[1,2]]，则输出将是[true，true]
为了解决这个问题，我们将遵循以下步骤-
N：=110
定义数组ret
在中定义一张映射
对于v中的每个元素，执行
在图表[it[0]]的末尾插入[1]
（将[it[1]]增加1）
定义一个队列q
对于初始化i：=0，当i<n时，更新（将i增加1），执行-
将我插入q
如果in[i]等于0，则-
定义一个映射IDX
对于初始化lvl：=1，当非q为空时，更新（将lvl增加1），执行-
节点：=q的第一个元素
从q删除元素
对于graph[node]中的每个元素
插入q
将x插入c[it]
（将[it]减少1）
对于c[node]中的每个元素x，
将节点插入c[it]
如果in[it]等于0，则-
sz：=q的大小
当sz不为0时，在每次迭代中减小sz，执行-
对于x中的每个元素，执行
在ret的末尾插入（在c[it[1]]中插入[it[0]的频率）
返回ret
例
让我们看下面的实现以更好地理解-
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<bool> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
const int N = 110;
class Solution {
public:
vector <int> graph[N];
map <int, set <int>> c;
vector<bool> checkIfPrerequisite(int n, vector<vector<int>>& v, vector<vector<int>>& x) {
vector<bool> ret;
map<int, int> in;
for (auto& it : v) {
graph[it[0]].push_back(it[1]);
in[it[1]]++;
}
queue<int> q;
for (int i = 0; i < n; i++) {
if (in[i] == 0)
q.push(i);
}
map<int, int> idx;
for (int lvl = 1; !q.empty(); lvl++) {
int sz = q.size();
while (sz--) {
int node = q.front();
q.pop();
for (auto& it : graph[node]) {
in[it]--;
for (auto& x : c[node])
c[it].insert(x);
c[it].insert(node);
if (in[it] == 0) {
q.push(it);
}
}
}
}
for (auto& it : x) {
ret.push_back(c[it[1]].count(it[0]));
}
return ret;
}
};
main(){
Solution ob;
vector<vector<int>> prerequisites = {{1,2},{1,0},{2,0}}, queries = {{1,0},{1,2}};
print_vector(ob.checkIfPrerequisite(3, prerequisites, queries));
}输入项
3, {{1,2},{1,0},{2,0}}, {{1,0},{1,2}}输出结果
[1, 1, ]