Tìm hành trình từ danh sách vé đã cho trong C++

Cho danh sách vé máy bay biểu diễn bằng cặp sân bay đi và đến [from, to], tìm hành trình theo thứ tự. Tất cả vé thuộc về một người khởi hành từ Chennai. Do đó hành trình phải bắt đầu từ Chennai.

Ví dụ: đầu vào [[\"Mumbai\", \"Kolkata\"], [\"Chennai\", \"Mumbai\"], [\"Delhi\", \"Bangalore\"], [\"Kolkata\", \"Delhi\"]], kết quả [\"Chennai\", \"Mumbai\", \"Kolkata\", \"Delhi\", \"Bangalore\"]

Các bước:

• Định nghĩa mảng ret và map graph.
• Định nghĩa phương thức visit(airport): trong khi graph[airport] không rỗng, lấy phần tử đầu x, xóa x khỏi graph[airport], gọi visit(x); thêm airport vào ret.
• Từ main: với mỗi vé, u = tickets[i][0], v = tickets[i][1], thêm v vào graph[u]; gọi visit(\"Chennai\"); đảo ngược ret và trả về.

Ví dụ (C++)

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
    cout << "[";
    for(int i = 0; i<v.size(); i++){
        cout << v[i] << ", ";
    }
    cout << "]"<<endl;
}
class Solution {
public:
    vector <string> ret;
    map < string, multiset <string> > graph;
    vector<string> findItinerary(vector<vector<string>>& tickets) {
        for(int i = 0; i < tickets.size(); i++){
            string u = tickets[i][0];
            string v = tickets[i][1];
            graph[u].insert(v);
        }
        visit("Chennai");
        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);
    }
};
main(){
    Solution ob;
    vector<vector<string>> v = {{\"Mumbai\", \"Kolkata\"}, {\"Chennai\", \"Mumbai\"}, {\"Delhi\", \"Bangalore\"}, {\"Kolkata\", \"Delhi\"}};
    print_vector(ob.findItinerary(v));
}

Đầu vào

{{\"Mumbai\", \"Kolkata\"}, {\"Chennai\", \"Mumbai\"}, {\"Delhi\", \"Bangalore\"}, {\"Kolkata\", \"Delhi\"}}

Đầu ra

[Chennai, Mumbai, Kolkata, Delhi, Bangalore, ]