C++-এ কোর্স শিডিউল IV

n সংখ্যক কোর্স আছে (০ থেকে n-1)। কিছু কোর্সের ডায়রেক্ট প্রি-রেকুইজিট আছে, যেমন কোর্স ০ নেওয়ার আগে কোর্স ১ নিতে হয় [1,0] দিয়ে এক্সপ্রেস করা হয়।

প্রশ্নের লিস্ট দেওয়া আছে, প্রতিটি প্রশ্নে চেক করতে হবে queries[i][0] কি queries[i][1] এর প্রি-রেকুইজিট (ডায়রেক্ট বা ইন্ডায়রেক্ট)। বুলিয়ান লিস্ট রিটার্ন করব।

ইনপুট: n=3, prerequisites=[[1,2],[1,0],[2,0]], queries=[[1,0],[1,2]] → আউটপুট: [true,true]

সমাধানের ধাপগুলো (টপোলজিক্যাল সর্ট + ট্রানজিটিভ ক্লোজার):

• ইন্ডিগ্রি কাউন্ট করে টপোলজিক্যাল অর্ডার বানাব

• প্রতি নোডের জন্য এর সব অ্যানসেস্টার সেট c[node] মেইনটেইন করব

• প্রসেসিংয় সময় চাইল্ডে প্যারেন্টের অ্যানসেস্টার কপি করব

• প্রশ্নের জন্য c[query[1]].count(query[0]) চেক করব

উদাহরণ

নিচের কোডটি দেখুন −

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