Tái tạo hành trình (Reconstruct Itinerary) trong C++

Mô tả bài toán

Cho danh sách vé máy bay [from, to]. Tất cả vé thuộc một người xuất phát từ "JFK". Tái tạo hành trình theo thứ tự từ điển nhỏ nhất (lexicographically smallest).

Ví dụ: [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]] → ["JFK","MUC","LHR","SFO","SJC"].

Giải thuật Hierholzer (Eulerian Path) + Multiset

1. Xây dựng đồ thị: map> (multiset tự động sắp xếp đến).
2. DFS từ "JFK": khi ở sân bay u, liên tục lấy đến nhỏ nhất v từ multiset, xóa và đệ quy visit(v).
3. Sau khi hết cạnh, push u vào kết quả (post-order).
4. Đảo ngược kết quả.

Đảm bảo đường đi Euler (duyệt mỗi cạnh đúng 1 lần) và thứ tự từ điển nhỏ nhất nhờ multiset.

Cài đặt C++

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

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

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

int main() {
    vector<vector<string>> v = {{"MUC","LHR"},{"JFK","MUC"},{"SFO","SJC"},{"LHR","SFO"}};
    Solution ob;
    print_vec(ob.findItinerary(v)); // [JFK, MUC, LHR, SFO, SJC]
    return 0;
}

Độ phức tạp

• Thời gian: O(E log E) (E = số vé, do multiset).
• Không gian: O(E).