C++-এ ইটিনারারি পুনর্নির্মাণ

এয়ারলাইন টিকিটের একটি তালিকা দেওয়া আছে যেগুলো প্রস্থান ও আগমন এয়ারপোর্টের জোড়া আকারে [from, to]। ক্রম অনুযায়ী ইটিনারারি পুনর্নির্মাণ করতে হবে। সব টিকিট একজন লোকের যিনি JFK থেকে প্রস্থান করেন। তাই ইটিনারারি অবশ্যই JFK-থেকে শুরু হবে।

উদাহরণ: ইনপুট [["MUC","LHR"], ["JFK","MUC"], ["SFO","SJC"], ["LHR","SFO"]] হলে আউটপুট ["JFK", "MUC", "LHR", "SFO", "SJC"]।

সমাধানের ধাপগুলো:

ret অ্যারে আর graph নামের একটি ম্যাপ সংজ্ঞায়িত করুন।
visit মেথড বানান যা এয়ারপোর্ট নাম নেবে:
- graph[airport]-র সাইজ ০ না হওয়া পর্যন্ত:
  - x := graph[airport]-র প্রথম উপাদান
  - graph[airport]-র প্রথম উপাদান ডিলিট করুন
  - visit(x) কল করুন
- ret-এ airport ঢোকান
মূল মেথড থেকে:
- i = 0 থেকে tickets.size()-1 পর্যন্ত:
  - u := tickets[i][0], v := tickets[i][1], graph[u]-এ v ইনসার্ট করুন
- 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, ]