第332题---Reconstruct Itinerary

• 题意描述

  • 给定一了一系列的pair，表示出发地到目的地，重新规划路线，同一出发地，不同目的地，按字母序排

• 思路

  • 其实就是一个图，深度优先搜索遍历
• 代码

  class Solution {
  public:
      vector<string> findItinerary(vector<pair<string, string>> tickets) {
          unordered_map<string, multiset<string>> graph;
          
          vector<string> itinerary;
          
          if(tickets.size() == 0)
              return itinerary;
          
          for(pair<string, string> eachTicket : tickets) {
              graph[eachTicket.first].insert(eachTicket.second);
          }
          
          stack<string> dfs;
          dfs.push("JFK");
          
          while(!dfs.empty()) {
              string topAirport = dfs.top();
              if(graph[topAirport].empty()) {
                  itinerary.push_back(topAirport);
                  dfs.pop();
              } else {
                  dfs.push(*(graph[topAirport].begin()));
                  graph[topAirport].erase(graph[topAirport].begin());
              }
          }
          
          reverse(itinerary.begin(), itinerary.end());
          return itinerary;
      }
  };