C++에서 여정 재구성

[from, to]와 같은 출발 및 도착 공항 쌍으로 표시되는 항공권 목록이 있다고 가정하면 여정을 순서대로 재구성해야 합니다. 모든 티켓은 JFK에서 출발하는 남성의 것입니다. 따라서 여정은 JFK로 시작해야 합니다.

따라서 입력이 [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]와 같으면 출력은 ["JFK", "MUC", "LHR", "SFO", "SJC"]입니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• 배열 ret와 graph라는 맵을 정의합니다.

• 방문이라는 메소드를 정의하십시오. 공항 이름을 입력으로 사용합니다.

• 그래프[공항]의 크기가 0이 아닌 동안

  • x :=그래프[공항]의 첫 번째 요소

  • 그래프[공항]에서 첫 번째 요소 삭제

  • 전화 방문(x)

• ret에 공항 삽입

• 이제 주요 방법에서 다음을 수행하십시오 -

• 범위 0에서 시세 배열 크기까지의 i에 대해

  • u :=티켓[i, 0], v :=티켓[i, 1], 그래프에 v 삽입[u]

• 첫 번째 공항이므로 방문(“JFK”)

• 목록을 뒤집고 ret 및 반환

예시(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, ]