मान लीजिए कुल n कोर्स हैं जिन्हें हम ले सकते हैं, कोर्स 0 से n-1 तक लेबल किए गए हैं।
कुछ कोर्स के डायरेक्ट प्रीरिक्विज़ाइट हो सकते हैं, उदाहरण के लिए, कोर्स 0 लेने के लिए हमें पहले कोर्स 1 लेना होगा, जिसे एक जोड़ी के रूप में व्यक्त किया जाता है: [1,0]।
इसलिए, यदि हमारे पास कोर्स की संख्या n, डायरेक्ट प्रीरिक्विज़ाइट जोड़ों की सूची और क्वेरी जोड़ों की सूची है।
आपको प्रत्येक queries[i] का उत्तर ढूंढना है कि क्या कोर्स queries[i][0], कोर्स queries[i][1] का प्रीरिक्विज़ाइट है या नहीं। अंत में, हमें बूलियन की एक सूची लौटानी है, जो दिए गए क्वेरी के उत्तर हैं।
हमें ध्यान रखना होगा कि यदि कोर्स a, कोर्स b का प्रीरिक्विज़ाइट है और कोर्स b, कोर्स c का प्रीरिक्विज़ाइट है, तो कोर्स a, कोर्स c का प्रीरिक्विज़ाइट है।
इसलिए, यदि इनपुट है n = 3, prerequisites = [[1,2],[1,0],[2,0]], queries = [[1,0],[1,2]], तो आउटपुट होगा [true,true]
इसे हल करने के लिए, हम निम्न चरणों का पालन करेंगे:
N := 110
एक ऐरे ret परिभाषित करें
एक मैप in परिभाषित करें
v के प्रत्येक एलिमेंट it के लिए, करें
it[1] को graph[it[0]] के अंत में डालें
(in[it[1]] को 1 से बढ़ाएं)
एक क्यू q परिभाषित करें
i := 0 से शुरू करें, जब i < n, i बढ़ाते हुए, करें -
यदि in[i], 0 के समान है, तो -
i को q में डालें
एक मैप idx परिभाषित करें
lvl := 1 से शुरू करें, जब q खाली नहीं है, lvl बढ़ाते हुए, करें -
sz := q का आकार
जब sz 0 नहीं है, प्रत्येक इटरेशन में sz घटाते हुए, करें -
node := q का पहला एलिमेंट
q से एलिमेंट हटाएं
graph[node] के प्रत्येक एलिमेंट it के लिए
(in[it] को 1 से घटाएं)
c[node] के प्रत्येक एलिमेंट x के लिए, करें
x को c[it] में डालें
node को c[it] में डालें
यदि in[it], 0 के समान है, तो -
it को q में डालें
x के प्रत्येक एलिमेंट it के लिए, करें
(it[0] की फ्रीक्वेंसी c[it[1]] में) को ret के अंत में डालें
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, ]
