ตารางหลักสูตร IV ใน C++

สมมติว่ามีทั้งหมด 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]] แล้ว ผลลัพธ์จะเป็น [จริง,จริง]

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• ไม่มี :=110

• กำหนดอาร์เรย์ ret

• กำหนดหนึ่งแผนที่ใน

• สำหรับแต่ละองค์ประกอบใน v ทำ

  • ใส่มัน[1] ที่ท้ายกราฟ[it[0]]

  • (เพิ่มขึ้นใน[มัน[1]] โดย 1)

• กำหนดหนึ่งคิว q

• สำหรับการเริ่มต้น i :=0 เมื่อ i

  • ถ้าใน[i] เท่ากับ 0 แล้ว −

    • แทรก i ลงใน q

• กำหนด idx ของแผนที่หนึ่งรายการ

• สำหรับการเริ่มต้น lvl :=1 เมื่อไม่มี q ว่าง ให้อัปเดต (เพิ่ม lvl ขึ้น 1) ทำ -

  • sz :=ขนาดของ q

  • ในขณะที่ sz ไม่ใช่ 0, ลด sz ในการวนซ้ำแต่ละครั้ง ให้ทำ -

    • โหนด :=องค์ประกอบแรกของ q

    • ลบองค์ประกอบออกจาก q

    • สำหรับแต่ละองค์ประกอบในกราฟ[โหนด]

      • (ลดลงใน[มัน] โดย 1)

      • สำหรับแต่ละองค์ประกอบ x ใน c[โหนด] ทำ

        • แทรก x ลงใน c[it]

      • แทรกโหนดลงใน c[it]

      • ถ้าใน[it] เท่ากับ 0 แล้ว −

        • แทรกลงใน q

• สำหรับแต่ละองค์ประกอบใน x ทำ

  • แทรก (ความถี่ของมัน[0] ใน c[it[1]]) ที่ส่วนท้ายของ 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, ]