C++의 주어진 티켓 목록에서 여정 찾기

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

따라서 입력이 [["Mumbai", " Kolkata"], ["Chennai ", " Mumbai"], ["Delhi", "Bangalore"], ["Kolkata", " Delhi"]]인 경우 출력은 ["Chennai", " Mumbai", " Kolkata", " Delhi", "Bangalore"]입니다.

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

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

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

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

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

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

  • 전화 방문(x)

• ret에 공항 삽입

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

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

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

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

• 목록을 뒤집고 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("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, ]