ধরুন মোট 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]], তাহলে আউটপুট হবে [সত্য, সত্য]
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
N :=110
-
একটি অ্যারে ret সংজ্ঞায়িত করুন
-
-এ একটি মানচিত্র সংজ্ঞায়িত করুন -
প্রতিটি উপাদানের জন্য এটি v, করুন
-
গ্রাফের শেষে এটি[1] সন্নিবেশ করুন[it[0]]
-
([এটি[1]] 1 দ্বারা বৃদ্ধি করুন)
-
-
এক সারি q
সংজ্ঞায়িত করুন -
আরম্ভ করার জন্য i :=0, যখন i
-
যদি in[i] 0 এর মত হয়, তাহলে −
-
q
-এ ঢোকান
-
-
-
একটি মানচিত্র idx সংজ্ঞায়িত করুন
-
lvl শুরু করার জন্য :=1, যখন q খালি না থাকে, আপডেট করুন (lvl 1 দ্বারা বাড়ান), করুন −
-
sz :=q এর আকার
-
যখন sz 0 না হয়, প্রতিটি পুনরাবৃত্তিতে sz হ্রাস করুন, −
করুন-
নোড :=q এর প্রথম উপাদান
-
q
থেকে উপাদান মুছুন -
প্রতিটি উপাদানের জন্য এটি গ্রাফ[নোড]
এ-
(1 দ্বারা [এটি] হ্রাস করুন)
-
c[নোড]-এ x প্রতিটি উপাদানের জন্য, করুন
-
c[it]
-এ x ঢোকান
-
-
c[it]
-এ নোড সন্নিবেশ করান -
যদি [এটি] 0 এর মত হয়, তাহলে −
-
এটি q
-এ ঢোকান
-
-
-
-
-
প্রতিটি উপাদানের জন্য এটি x, করুন
-
ret এর শেষে সন্নিবেশ করান (এর ফ্রিকোয়েন্সি[0] c[it[1]]
-
-
রিটার্ন রিটার্ন
উদাহরণ
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
#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, ]
