মান লিজিয়ে, 2n টি চিঠি আছে এবং প্রতিটি চিঠিতে ১ থেকে n পর্যন্ত একটি পূর্ণসংখ্যা লেখা আছে। প্রতিটি সংখ্যার জন্য ঠিক দুটি চিঠি আছে। এই চিঠিগুলো m টি স্টকে সাজানো আছে এবং i-তম স্টকে stacks[i] চিঠি আছে। আমাদের কাজ হলো সব স্টকে নিচের পদ্ধতিতে খালি করা:
যেকোনো দুটি স্টক বেছে নিতে হবে এবং উভয় স্টকের উপরের চিঠি সরিয়ে ফেলতে হবে।
সরানো চিঠ দুটির উপরে একই সংখ্যা থাকতে হবে।
যদি আমরা এই পদ্ধতিতে m টি স্টক খালি করতে পারি, তবে true প্রিন্ট করব, অন্যথায় false রিটার্ন করব।
যেমন, ইনপুট হলে n = 3, m = 2, stacks = {{2, 1, 3}, {2, 1, 3}}, তবে আউটপুট হবে true।
দুটি স্টক আছে এবং প্রতিটি স্টকে চিঠিগুলোতে ২, ১, ৩ নম্বর লেখা আছে। তাই আমরা দুটি স্টক থেকে চিঠি সরিয়ে সেগুলো খালি করতে পারি।
সমাধানের ধাপসমূহ
এই সমস্যাটি সমাধান করার জন্য নিচের ধাপগুলো অনুসরণ করব:
dp ২D অ্যারে সংজ্ঞায়িত করুন tvec অ্যারে সংজ্ঞায়িত করুন i := 0 থেকে m-1 পর্যন্ত: k := stacks[i]-র আকার j := 0 থেকে k-1 পর্যন্ত: if j < 0, তবে: dp[stacks[i, j]]-র শেষে p যোগ করুন tvec[p] ১ বাড়িয়ে p := stacks[i, j] tp অ্যারে সংজ্ঞায়িত করুন i := 1 থেকে n পর্যন্ত: একটি q কিউ সংজ্ঞায়িত করুন q-তে i যোগ করুন while (q খালি নয়): if not tp[q-র প্রথম উপাদান] এবং tvec[q-র প্রথম উপাদান] == 0, তবে: dp[q-র প্রথম উপাদান]-র প্রতিটি next উপাদানের জন্য: tvec[next] ১ কমিয়ে q-তে next যোগ করুন tp[q-র প্রথম উপাদান] := true q-র প্রথম উপাদান মুছুন i := 1 থেকে n পর্যন্ত: if tvec[i] != 0, তবে: return false return 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
