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

Cho n khóa học (0 đến n-1), danh sách điều kiện tiên quyết trực tiếp prerequisites (cặp [u,v]: u trước v), và các truy vấn queries. Xác định cho mỗi truy vấn [u,v] có u là điều kiện tiên quyết (trực tiếp hoặc gián tiếp) của v hay không.

Ví dụ

Đầu vào: n=3, prerequisites=[[1,2],[1,0],[2,0]], queries=[[1,0],[1,2]]
Đầu ra: [true,true].

Thuật toán Topological Sort + Truyền tập tiền đề

1. Xây dựng đồ thị và mảng indegree.
2. Kahn's algorithm (BFS topo): hàng đợi các đỉnh indegree 0.
3. Mảng pre[i] = set chứa tất cả tiền đề của i.
4. Khi xử lý đỉnh u: với mỗi đỉnh kề v, gộp pre[u] vào pre[v] và thêm u vào pre[v].
5. Trả lời truy vấn: kiểm tra u in pre[v].

Triển khai C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    vector<bool> checkIfPrerequisite(int n, vector<vector<int>>& pre, vector<vector<int>>& queries) {
        vector<vector<int>> g(n);
        vector<int> indeg(n);
        for (auto& e : pre) {
            g[e[0]].push_back(e[1]);
            indeg[e[1]]++;
        }
        vector<set<int>> preSet(n);
        queue<int> q;
        for (int i = 0; i < n; ++i) if (indeg[i] == 0) q.push(i);
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (int v : g[u]) {
                preSet[v].insert(u);
                preSet[v].insert(preSet[u].begin(), preSet[u].end());
                if (--indeg[v] == 0) q.push(v);
            }
        }
        vector<bool> ans;
        for (auto& q : queries) ans.push_back(preSet[q[1]].count(q[0]));
        return ans;
    }
};

Độ phức tạp

• Thời gian: O(N^2 + E) trong trường hợp xấu (gộp set), N ≤ 100 theo constraints.
• Không gian: O(N^2) cho các set tiền đề.

Kết quả kiểm thử

Đầu vào: 3, {{1,2},{1,0},{2,0}}, {{1,0},{1,2}}
Đầu ra: [1, 1] (true, true)