मान लीजिए कि हमारे पास 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