Lịch trình khóa học IV trong C ++

Giả sử có tổng cộng n khóa học chúng ta có thể tham gia, các khóa học được đánh dấu từ 0 đến n-1.

Một số khóa học có thể có các điều kiện tiên quyết trực tiếp, chẳng hạn như để học khóa 0, trước tiên chúng ta phải tham gia khóa học 1, được biểu thị dưới dạng một cặp:[1,0].

Vì vậy, nếu chúng ta có một số khóa học n, một danh sách các cặp điều kiện tiên quyết trực tiếp và một danh sách các cặp truy vấn.

Bạn nên tìm câu trả lời cho mỗi truy vấn [i] cho dù các truy vấn khóa học [i] [0] có phải là điều kiện tiên quyết của các truy vấn khóa học [i] [1] hay không. Cuối cùng, chúng ta phải trả về một danh sách boolean, câu trả lời cho các truy vấn đã cho.

Chúng ta phải lưu ý rằng nếu khóa học a là điều kiện tiên quyết của khóa học b và khóa học b là điều kiện tiên quyết của khóa học c, thì khóa học a là điều kiện tiên quyết của khóa học c.

Vì vậy, nếu đầu vào giống như n =3, điều kiện tiên quyết =[[1,2], [1,0], [2,0]], truy vấn =[[1,0], [1,2]], thì đầu ra sẽ là [true, true]

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• N:=110

• Xác định ret mảng

• Xác định một bản đồ trong

• đối với mỗi phần tử nó trong v, thực hiện

  • chèn nó [1] vào cuối biểu đồ [nó [0]]

  • (tăng [it [1]] lên 1)

• Xác định một hàng đợi q

• để khởi tạo i:=0, khi i

  • nếu trong [i] giống với 0, thì -

    • chèn tôi vào q

• Xác định một idx bản đồ

• để khởi tạo lvl:=1, khi không phải q trống, hãy cập nhật (tăng lvl lên 1), thực hiện -

  • sz:=kích thước của q

  • trong khi sz không phải là 0, hãy giảm sz trong mỗi lần lặp, thực hiện -

    • node:=phần tử đầu tiên của q

    • xóa phần tử khỏi q

    • cho mỗi phần tử nó trong biểu đồ [node]

      • (giảm [it] đi 1)

      • đối với mỗi phần tử x trong c [node], thực hiện

        • chèn x vào c [it]

      • chèn nút vào c [it]

      • nếu trong [nó] giống 0, thì -

        • chèn nó vào q

• đối với mỗi phần tử nó trong x, thực hiện

  • chèn (tần suất của nó [0] trong c [nó [1]]) vào cuối ret

• trả lại ret

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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));
}

Đầu vào

3, {{1,2},{1,0},{2,0}}, {{1,0},{1,2}}

Đầu ra

[1, 1, ]