मान लीजिए हमारे पास प्रस्थान और आगमन हवाई अड्डों के जोड़े द्वारा दर्शाए गए टिकटों की एक सूची है जैसे [from, to], हमें क्रम में यात्रा कार्यक्रम ढूंढना है। सभी टिकट एक आदमी के हैं जो चेन्नई से प्रस्थान करता है। इसलिए, यात्रा कार्यक्रम चेन्नई से शुरू होना चाहिए।
तो यदि इनपुट [["Mumbai", " Kolkata"], ["Chennai ", " Mumbai"], ["Delhi", "Bangalore"], ["Kolkata", " Delhi"]] जैसा है, तो आउटपुट ["Chennai", " Mumbai", " Kolkata", " Delhi", "Bangalore"] होगा।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे −
ret नामक एक सरणी और graph नामक एक मैप परिभाषित करें।
visit नामक एक विधि परिभाषित करें। यह हवाई अड्डे का नाम इनपुट के रूप में लेगा
जब तक graph[airport] का आकार 0 नहीं है
x := graph[airport] का पहला तत्व
graph[airport] से पहला तत्व हटाएं
visit(x) कॉल करें
airport को ret में डालें
अब मुख्य विधि से, निम्नलिखित करें −
i को 0 से टिकट सरणी के आकार तक की रेंज में
u := tickets[i, 0], v := tickets[i, 1], v को graph[u] में डालें
visit("Chennai") कॉल करें क्योंकि यह पहला हवाई अड्डा है
ret सूची को उल्टा करें और लौटाएं
उदाहरण (C++)
बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें −
#include <bits/stdc++.h> using namespace std; void print_vector(vector<auto> v){ cout << "["; for(int i = 0; i<v.size(); i++){ cout << v[i] << ", "; } cout << "]"<<endl; } class Solution { public: vector <string> ret; map < string, multiset <string> > graph; vector<string> findItinerary(vector<vector<string>>& tickets) { for(int i = 0; i < tickets.size(); i++){ string u = tickets[i][0]; string v = tickets[i][1]; graph[u].insert(v); } visit("Chennai"); reverse(ret.begin(), ret.end()); return ret; } void visit(string airport){ while(graph[airport].size()){ string x = *(graph[airport].begin()); graph[airport].erase(graph[airport].begin()); visit(x); } ret.push_back(airport); } }; main(){ Solution ob; vector<vector<string>> v = {{"Mumbai", "Kolkata"}, {"Chennai", "Mumbai"}, {"Delhi", "Bangalore"}, {"Kolkata", "Delhi"}}; print_vector(ob.findItinerary(v)); }इनपुट
{{"Mumbai", "Kolkata"}, {"Chennai", "Mumbai"}, {"Delhi", "Bangalore"}, {"Kolkata", "Delhi"}}आउटपुट
[Chennai, Mumbai, Kolkata, Delhi, Bangalore, ]