मान लीजिए हमारे पास x-अक्ष पर n बिंदु हैं और बिंदुओं के बीच अनुमत संक्रमणों की सूची है। पता करें कि क्या इन संक्रमणों के माध्यम से प्रारंभिक बिंदु से अंत तक पहुंचना संभव है। इसलिए यदि बिंदुओं x1 और x2 के बीच एक संक्रमण है, तो हम बिंदु x से 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
