C++ में यात्रा कार्यक्रम का पुनर्निर्माण

मान लीजिए हमारे पास एयरलाइन टिकटों की एक सूची है जो प्रस्थान और आगमन हवाई अड्डों के जोड़े द्वारा दर्शाई गई है जैसे [from, to], हमें क्रम में यात्रा कार्यक्रम का पुनर्निर्माण करना है। सभी टिकट एक आदमी के हैं जो JFK से प्रस्थान करता है। इसलिए, यात्रा कार्यक्रम JFK से शुरू होना चाहिए।

उदाहरण के लिए, यदि इनपुट [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]] जैसा है, तो आउटपुट ["JFK", "MUC", "LHR", "SFO", "SJC"] होगा।

इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे:

• ret नामक सरणी और graph नामक मैप परिभाषित करें।
• visit नामक एक विधि परिभाषित करें। यह हवाई अड्डे का नाम इनपुट के रूप में लेगा
• जब तक graph[हवाई अड्डा] का आकार 0 नहीं है
  • x := graph[हवाई अड्डा] का पहला तत्व
  • graph[हवाई अड्डा] से पहला तत्व हटाएं
  • visit(x) कॉल करें
• हवाई अड्डा को ret में डालें
• अब मुख्य विधि से, निम्नलिखित करें:
  • i को 0 से टिकट सरणी के आकार तक लूप करें
    • u := tickets[i, 0], v := tickets[i, 1], v को graph[u] में डालें
  • visit("JFK") कॉल करें क्योंकि यह पहला हवाई अड्डा है
  • 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("JFK");       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 = {{"MUC","LHR"},{"JFK","MUC"},{"SFO","SJC"},{"LHR","SFO"}};    print_vector(ob.findItinerary(v)); }

इनपुट

[["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]

आउटपुट

[JFK, MUC, LHR, SFO, SJC, ]