मान लीजिए 2n अक्षर हैं और प्रत्येक पर 1 से n के बीच एक पूर्णांक लिखा है। प्रत्येक संख्या वाले ठीक दो अक्षर हैं। ये अक्षर m स्टैक्स में व्यवस्थित हैं और स्टैक i में अक्षर stack[i] हैं। हमारा कार्य निम्न तरीके से सभी स्टैक्स को खाली करना है:
- किसी भी दो स्टैक्स को चुनें और दोनों से शीर्ष अक्षर हटाएँ।
- हटाए गए दोनों अक्षरों पर समान संख्या लिखी होनी चाहिए।
यदि हम इस तरीके से m स्टैक्स को खाली कर सकते हैं, तो true प्रिंट करें अन्यथा false लौटाएँ।
उदाहरण के लिए, यदि इनपुट है n = 3, m = 2, stacks = {{2, 1, 3}, {2, 1, 3}}, तो आउटपुट true होगा।
दो स्टैक्स हैं और प्रत्येक में क्रमशः 2, 1, 3 संख्या वाले अक्षर हैं। इसलिए हम दोनों स्टैक्स से हटाकर उन्हें दिए गए तरीके से खाली कर सकते हैं।
चरण
इसे हल करने के लिए हम निम्न चरणों का पालन करेंगे:
एक 2D सरणी dp परिभाषित करें
एक सरणी tvec परिभाषित करें
i := 0 से m-1 तक:
k := stacks[i] का आकार
j := 0 से k-1 तक:
यदि j > 0, तो:
dp[stacks[i][j]] के अंत में p डालें
tvec[p] बढ़ाएँ
p := stacks[i][j]
आकार n+1 का सरणी tp परिभाषित करें
i := 1 से n तक:
एक कतार q परिभाषित करें
i को q में डालें
जब तक q खाली न हो:
यदि tp[q का पहला तत्व] असत्य है और tvec[q का पहला तत्व] == 0, तो:
dp[q का पहला तत्व] में प्रत्येक तत्व next के लिए:
tvec[next] घटाएँ
next को q में डालें
tp[q का पहला तत्व] := true
q से पहला तत्व हटाएँ
i := 1 से n तक:
यदि tvec[i] != 0, तो:
false लौटाएँ
true लौटाएँ
उदाहरण
बेहतर समझ के लिए निम्न कार्यान्वयन देखें:
#include <bits/stdc++.h> using namespace std; bool solve(int n, int m, vector<vector<int>> stacks){ vector<vector<int>> dp(n + 1); vector<int> tvec(n + 1); for(int i = 0; i < m; i++){ int k = stacks[i].size(); int p; for(int j = 0; j < k; j++){ if(j > 0){ dp[stacks[i][j]].push_back(p); tvec[p]++; } p = stacks[i][j]; } } vector<bool> tp(n + 1); for(int i = 1; i <= n; i++){ queue<int> q; q.push(i); while(!q.empty()){ if(!tp[q.front()] && tvec[q.front()] == 0){ for(auto next: dp[q.front()]){ tvec[next]--; q.push(next); } tp[q.front()]=true; } q.pop(); } } for(int i = 1; i <= n; i++){ if(tvec[i] != 0){ return false; } } return true; } int main() { int n = 3, m = 2; vector<vector<int>> stacks = {{2, 1, 3}, {2, 1, 3}}; cout<< solve(n, m, stacks); return 0; }
इनपुट
3, 2, {{2, 1, 3}, {2, 1, 3}}
आउटपुट
1
