C++で指定されたチケットのリストから旅程を検索します

[from、to]のような出発空港と到着空港のペアで表されるチケットのリストがあるとすると、旅程を順番に見つける必要があります。チケットはすべてチェンナイを出発する男性のものです。したがって、旅程はチェンナイで始まる必要があります。

したがって、入力が[["Mumbai"、 "Kolkata"]、["Chennai"、 "Mumbai"]、["Delhi"、 "Bangalore"]、["Kolkata"、 "Delhi"]]の場合、出力は["Chennai"、 "Mumbai"、 "Kolkata"、 "Delhi"、"Bangalore"]になります。

これを解決するには、次の手順に従います-

• 配列retとグラフと呼ばれるマップを定義します。

• visitというメソッドを定義します。これは入力として空港名を取ります

• グラフ[空港]のサイズが0ではない場合

  • x：=グラフの最初の要素[空港]

  • グラフから最初の要素を削除します[空港]

  • コールvisit（x）

• 空港をretに挿入

• ここで、mainメソッドから、次のようにします-

• 0からティッカー配列のサイズまでの範囲のiの場合

  • u：=チケット[i、0]、v：=チケット[i、1]、グラフにvを挿入[u]

• これが最初の空港なので、visit（“ Chennai”）

• リストを逆にして戻る

例（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));
}

入力

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

出力

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