C++-এ সিটি ভিজিটের সঠিক ক্রম খুঁজে বের করার প্রোগ্রাম

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

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

সমাধানের ধাপসমূহ

• ret অ্যারে এবং graph ম্যাপ সংজ্ঞায়িত করুন।
• visit(airport) মেথড: যতক্ষণ graph[airport] খালি নয়, x = প্রথম উপাদান, মুছুন, visit(x) কল করুন। airport ret-এ ইনসার্ট করুন।
• মূল মেথড: টিকিটগুলো থেকে graph বানান, visit("KLK") কল করুন, ret রিভার্স করে ফেরত দিন।

উদাহরণ কোড (C++)

#include 
using namespace std;
void print_vector(vector v){
    cout << "[";
    for(int i = 0; i ret;
    map> 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("KLK");
        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> v ={{"MUC","LHR"},{"KLK","MUC"},{"SFO","SJC"},{"LHR","SFO"}};
    print_vector(ob.findItinerary(v));
}

ইনপুট

{{"MUC","LHR"},{"KLK","MUC"},{"SFO","SJC"},{"LHR","SFO"}}

আউটপুট

[KLK, MUC, LHR, SFO, SJC, ]