โปรแกรมหาลำดับการเดินทางที่ถูกต้องจากตั๋วเครื่องบินใน C++

สมมติว่าเรามีรายการตั๋วเครื่องบินเป็นคู่ [from, to] ต้องสร้างเส้นทางเดินทาง (itinerary) ให้ถูกต้อง เริ่มจาก "KLK" (ในโจทย์ต้นฉบับคือ "JFK")

ตัวอย่าง: [["MUC","LHR"],["KLK","MUC"],["SFO","SJC"],["LHR","SFO"]] → ["KLK","MUC","LHR","SFO","SJC"]

ขั้นตอนการแก้ปัญหา (Hierholzer's Algorithm / Eulerian Path)

1. สร้าง graph เป็น map: airport → multiset ของ destinations (เรียงลำดับ)
2. ฟังก์ชัน visit(airport):
   • while graph[airport] ไม่ว่าง:
     • pop destination แรกออก
     • เรียก visit(dest) recursive
   • เพิ่ม airport เข้า ret
3. เรียก visit("KLK")
4. กลับลำดับ ret และคืนค่า

ตัวอย่างโค้ด C++

#include 
using namespace std;

void print_vector(vector v) {
    cout << "[";
    for(int i = 0; i < v.size(); i++) {
        cout << v[i] << ", ";
    }
    cout << "]" << endl;
}

class Solution {
public:
    vector ret;
    map> graph;
    
    vector findItinerary(vector>& tickets) {
        for(auto& t : tickets) {
            graph[t[0]].insert(t[1]);
        }
        visit("KLK");
        reverse(ret.begin(), ret.end());
        return ret;
    }
    
    void visit(string airport) {
        while(!graph[airport].empty()) {
            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"},{"KLK","MUC"},{"SFO","SJC"},{"LHR","SFO"}};
    print_vector(ob.findItinerary(v));
    // Output: [KLK, MUC, LHR, SFO, SJC, ]
}

อินพุต

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

เอาต์พุต

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