สร้างเส้นทางการบินใหม่ใน C++

ให้รายการตั๋วเครื่องบิน [from, to] ทั้งหมดเป็นของคนเดียวกัน เริ่มจาก JFK ต้องสร้างเส้นทาง (itinerary) ใช้ตั๋วทุกใบพอดี 1 ใบ หากมีหลายทาง ให้เลือกทางที่ lexical order น้อยที่สุด

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

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

1. สร้างกราฟ map> (multiset เรียง lexical อัตโนมัติ)
2. DFS (post-order) จาก "JFK":
   • จนกว่าจะไม่มีทางออก: ดึงจุดหมายแรกจาก multiset, ลบออก, เรียก DFS ต่อ
   • เมื่อไม่มีทางออกแล้ว ใส่โหนดปัจจุบันเข้า ret
3. กลับลำดับ ret (post-order → ต้อง reverse)

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

#include <bits/stdc++.h>
using namespace std;

void print_vector(vector<string> v) {
    cout << "[";
    for (auto& s : v) cout << s << ", ";
    cout << "]" << endl;
}

class Solution {
public:
    vector<string> ret;
    map<string, multiset<string>> graph;
    vector<string> findItinerary(vector<vector<string>>& tickets) {
        for (auto& t : tickets) graph[t[0]].insert(t[1]);
        visit("JFK");
        reverse(ret.begin(), ret.end());
        return ret;
    }
    void visit(string airport) {
        while (!graph[airport].empty()) {
            string next = *graph[airport].begin();
            graph[airport].erase(graph[airport].begin());
            visit(next);
        }
        ret.push_back(airport);
    }
};

int main() {
    Solution ob;
    vector<vector<string>> v = {{"MUC","LHR"},{"JFK","MUC"},{"SFO","SJC"},{"LHR","SFO"}};
    print_vector(ob.findItinerary(v));
}

Input

[["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]

Output

[JFK, MUC, LHR, SFO, SJC, ]