C++で旅程を再構築する

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

したがって、入力が[["MUC"、 "LHR"]、["JFK"、 "MUC"]、["SFO"、 "SJC"]、["LHR"、 "SFO"]]の場合、出力は["JFK"、 "MUC"、 "LHR"、 "SFO"、"SJC"]になります。

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

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

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

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

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

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

  • コールvisit（x）

• 空港をretに挿入

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

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

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

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

• リストを逆にして戻る

例（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("JFK");
      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 = {{"MUC","LHR"},{"JFK","MUC"},{"SFO","SJC"},{"LHR","SFO"}};
   print_vector(ob.findItinerary(v));
}

入力

[["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]

出力

[JFK, MUC, LHR, SFO, SJC, ]