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

Giả sử chúng ta có một danh sách các vé được đại diện bởi các cặp sân bay đi và đến như [from, to], chúng ta phải tìm hành trình theo thứ tự. Tất cả các vé thuộc về một người đàn ông khởi hành từ Chennai. Vì vậy, hành trình phải bắt đầu với Chennai.

Vì vậy, nếu đầu vào là [["Mumbai", "Kolkata"], ["Chennai", "Mumbai"], ["Delhi", "Bangalore"], ["Kolkata", "Delhi"]], thì đầu ra sẽ là ["Chennai", "Mumbai", "Kolkata", "Delhi", "Bangalore"].

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định mảng ret và một bản đồ được gọi là đồ thị.

• Xác định một phương pháp được gọi là thăm. Điều này sẽ lấy tên sân bay làm đầu vào

• trong khi kích thước của biểu đồ [sân bay] không phải là 0

  • x:=phần tử đầu tiên của biểu đồ [sân bay]

  • xóa phần tử đầu tiên khỏi biểu đồ [airport]

  • gọi đến thăm (x)

• chèn sân bay vào ret

• Bây giờ từ phương thức chính, hãy làm như sau -

• cho tôi trong phạm vi 0 đến kích thước của mảng mã

  • u:=ticket [i, 0], v:=ticket [i, 1], chèn v vào biểu đồ [u]

• thăm (“Chennai”) vì đây là sân bay đầu tiên

• đảo ngược danh sách lại và quay lại

Ví dụ (C ++)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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, ]