ধরুন আমাদের x-অক্ষে n পয়েন্ট রয়েছে এবং বিন্দুগুলির মধ্যে অনুমোদিত অনুবাদের তালিকা রয়েছে। শুধুমাত্র এই লেনদেনের মাধ্যমে শুরু থেকে শেষ পর্যন্ত পৌঁছানো সম্ভব কিনা তা খুঁজুন। সুতরাং যদি x1 এবং x2 বিন্দুর মধ্যে একটি অনুবাদ থাকে, তাহলে আমরা x বিন্দু থেকে x1 এবং x2 এর মধ্যবর্তী যেকোনো বিন্দুতে বা সরাসরি x2-এ যেতে পারি। তাই যদি n =5। এবং লেনদেন হয় 0 থেকে 2, 2 থেকে 4 এবং 3 থেকে 5। তাহলে আউটপুট হবে হ্যাঁ। 0→2→3→5.
থেকে একটি পথ আছেআমাদের জোড়ার প্রথম উপাদান অনুযায়ী তালিকা সাজাতে হবে। তারপর তালিকার দ্বিতীয় জোড়া থেকে শুরু করুন এবং জুটির প্রথম উপাদানটি পূর্ববর্তী জোড়ার দ্বিতীয় উপাদান এবং বর্তমান জোড়ার দ্বিতীয় উপাদানের মধ্যে আছে কিনা তা পরীক্ষা করুন। এই শর্তটি পরপর দুটি জোড়ার মধ্যে একটি পথ আছে কিনা তা পরীক্ষা করতে ব্যবহৃত হয়। শেষে আমরা পরীক্ষা করব যে আমরা যে পয়েন্টে পৌঁছেছি সেটি গন্তব্য বিন্দু এবং যে পয়েন্ট থেকে আমরা শুরু করেছি সেটি হল স্টার্ট পয়েন্ট। যদি তাই হয় তবে হ্যাঁ প্রদর্শন করুন অন্যথায় না প্রদর্শন করুন৷
উদাহরণ
#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
