C++-এ টিকেটের লিস্ট থেকে যাত্রাপথ (Itinerary) নির্ণয়

প্রস্থান এবং আগমন এয়ারপোর্টের জোড়া হিসেবে টিকেটের লিস্ট দেওয়া আছে। চেন্নাই থেকে যাত্রা শুরু করে সঠিক ক্রমে যাত্রাপথ খুঁজে বের করুন।

ইনপুট: [["Mumbai","Kolkata"],["Chennai","Mumbai"],["Delhi","Bangalore"],["Kolkata","Delhi"]]

আউটপুট: ["Chennai","Mumbai","Kolkata","Delhi","Bangalore"]

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

• গ্রাফ তৈরি করুন: প্রতিটি প্রস্থান এয়ারপোর্ট থেকে আগমন এয়ারপোর্টের মাল্টিসেট (multiset) রাখুন।
• DFS-ভিত্তিক visit() ফাংশন: কারেন্ট এয়ারপোর্ট থেকে সব আউটগোইং এজ ট্রাভার্স করুন, এজ মুছে ফেলুন, রিকার্সিভ কল দিন।
• ভিজিট শেষে এয়ারপোর্টকে রেজাল্ট ভেক্টরে পুশ করুন।
• শেষে রেজাল্ট রিভার্স করুন।

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

#include <bits/stdc++.h>
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> 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, ]