x-অক্ষে n সংখ্যক পয়েন্ট এবং তাদের মধ্যে অনুমোদিত ট্রানজিশন (transition) বা স্থানান্তরের তালিকা দেওয়া আছে। শুধু এই ট্রানজিশনগুলো ব্যবহার করে শুরুর পয়েন্ট থেকে শেষ পয়েন্টে পৌঁছানো সম্ভব কিনা তা খুঁজে বের করতে হবে। যদি x1 এবং x2 পয়েন্টের মধ্যে ট্রানজিশন থাকে, তবে x1 থেকে x1 এবং x2-এর মাঝপথের যেকোনো পয়েন্টে বা সরাসরি x2-এ যাওয়া যাবে। উদাহরণস্বরূপ, n = 5। এবং ট্রানজিশনগুলো: 0 থেকে 2, 2 থেকে 4, এবং 3 থেকে 5। আউটপুট হবে YES। পথ আছে 0→2→3→5।
পেয়ারগুলোকে প্রথম এলিমেন্ট অনুযায়ী সর্ট করতে হবে। তারপর লিস্টের দ্বিতীয় পেয়ার থেকে শুরু করে চেক করব যে, করেন্ট পেয়ারের প্রথম এলিমেন্ট, প্রিভিয়াস পেয়ারের দ্বিতীয় এলিমেন্ট এবং করেন্ট পেয়ারের দ্বিতীয় এলিমেন্টের মাঝপথে আছে কিনা। এই শর্ত দুটি কনসিকিউটিভ পেয়ারের মধ্যে পথ আছে কিনা তা চেক করে। শেষে চেক করব যে আমরা যে পয়েন্টে পৌঁছেছি সেটি ডেস্টিনেশন পয়েন্ট কিনা এবং শুরুর পয়েন্ট ০ কিনা। যদি হয় তবে YES দেখাব, অন্যথায় NO।
উদাহরণ
#include <iostream> #include <vector> #include <map> #include <algorithm> using namespace std; bool isPathPairFound(int n, vector<pair<int, int> > array) { sort(array.begin(),array.end()); int start_point = array[0].first; int end_point=array[0].second; for (int i=1; i<n; i++) { if (array[i].first > end_point) break; end_point=max(end_point,array[i].second); } return (n <= end_point && start_point==0); } int main() { vector<pair<int, int> > array; array.push_back(make_pair(0,2)); array.push_back(make_pair(2,4)); array.push_back(make_pair(3,5)); if (isPathPairFound(5,array)) cout << "Path has found"; else cout << "NO Path has found"; }আউটপুট
Path has found
