C++ 课程表 IV

c++server side programmingprogramming

假设我们总共可以选修 n 门课程，这些课程的编号从 0 到 n-1。

有些课程可能有直接的先决条件，例如，要选修课程 0，我们必须先选修课程 1，这表示为一对:[1,0]。

因此，如果我们有课程数 n，则有一个直接先决条件对列表和一个查询对列表。

您应该为每个查询 [i] 找到答案，看看课程查询 [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[1] 插入 graph[it[0]] 末尾
- (将 in[it[1]] 增加 1)
定义一个队列 q
初始化 i := 0，当 i < n 时，更新(将 i 增加 1)，执行 −
- 如果 in[i] 与 0 相同，则 −
  - 将 i 插入 q
定义一个映射 idx
初始化 lvl := 1，当 q 不为空时，更新(将 lvl 增加 1)，执行 −
- sz := q 的大小
- 当 sz 不为 0 时，在每次迭代中减少 sz，执行 −
  - node := q 的第一个元素
  - 从 q 中删除元素
  - 对于 graph[node] 中的每个元素 it
    - (将 in[it] 减少 1)
    - 对于 c[node] 中的每个元素 x，执行
      - 将 x 插入 c[it]
    - 将节点插入 c[it]
    - 如果 in[it] 与 0 相同，则 −
      - 将其插入 q
对于 x 中的每个元素 it，执行
- 在 ret 末尾插入 (it[0] 在 c[it[1]] 中的频率)
return 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));
}