ตารางเรียน IV ใน C++

สมมติว่ามี n วิชา หมายเลข 0 ถึง n-1 บางวิชามี prerequisite โดยตรง เช่น [1,0] หมายถึงต้องเรียน 1 ก่อน 0 กำหนด n, prerequisite pairs, และ queries เราต้องตอบว่า queries[i][0] เป็น prerequisite ของ queries[i][1] หรือไม่ (รวม indirect)

ตัวอย่าง: n=3, prerequisites=[[1,2],[1,0],[2,0]], queries=[[1,0],[1,2]] ผลลัพธ์=[true,true]

วิธีแก้ปัญหา (Topological Sort + Transitive Closure)

1. สร้างกราฟและ indegree จาก prerequisites
2. Topological sort (Kahn's algorithm) ประมวลผลทีละ level
3. แต่ละโหนดเก็บ set ของ prerequisites ทั้งหมด (transitive closure)
4. เมื่อประมวลผล node ให้ merge prerequisites ไปยัง neighbors
5. ตอบ query โดยเช็คว่า course อยู่ใน set ของอีก course หรือไม่

ตัวอย่างโค้ด C++

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

int 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, ]