C++ में देखे गए शहरों के सही क्रम को खोजने का प्रोग्राम

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

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

इसे हल करने के लिए हम निम्न चरणों का पालन करेंगे (हायरार्किकल DFS / ऑयलर पथ):

• ret सरणी और graph मैप परिभाषित करें।

• visit(airport) मेथड परिभाषित करें:

  • जब तक graph[airport] का आकार 0 नहीं है:

    • x := graph[airport] का पहला तत्व।

    • graph[airport] से पहला तत्व हटाएं।

    • visit(x) कॉल करें।

  • ret में airport जोड़ें।

• मुख्य विधि से:

  • प्रत्येक टिकट के लिए: u = ticket[0], v = ticket[1], graph[u].insert(v)।

  • visit("JFK") कॉल करें।

  • ret को उल्टा करें और लौटाएं।

उदाहरण

#include  using namespace std; void print_vector(vector v){    cout << "[";    for(int i = 0; i ret;    map < string, multiset  > graph;    vector findItinerary(vector>& 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);    } }; int main(){    Solution ob;    vector> 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, ]