Chương trình tìm thứ tự thành phố thăm đúng trong C++

Cho danh sách vé máy bay [from, to], tái tạo hành trình đúng thứ tự. Hành trình bắt đầu từ "JFK" (trong code là "KLK").

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

Giải thuật (Hierholzer - Eulerian Path)

1. Xây đồ thị : map từ sân bay đến multiset các sân bay đến (tự động sắp xếp).
2. DFS :
   • Khi không rỗng: lấy sân bay đầu tiên, xóa, đệ quy .
   • Thêm vào kết quả .
3. Gọi , đảo ngược và trả về.

Ví dụ minh họa (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].size()) {
            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));
}

Đầu vào

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

Đầu ra

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