SHARE
TWEET

Untitled

a guest Aug 20th, 2019 67 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Solution {
  2. public:
  3.     vector<string> findItinerary(vector<vector<string>>& tickets) {
  4.        
  5.         // 构建邻接表
  6.         for(const auto& ticket: tickets) {
  7.             trip[ticket[0]].push_back(ticket[1]);
  8.         }
  9.        
  10.         // 邻接表按字典序排序
  11.         for(auto& pair: trip) {
  12.             auto& dest = pair.second;
  13.             sort(dest.begin(), dest.end());
  14.         }
  15.        
  16.         const string start = "JFK";  // 开始顶点
  17.        
  18.         dfs(start);
  19.        
  20.         return vector<string>(route.crbegin(), route.crend());
  21.     }
  22.    
  23. private:
  24.     unordered_map<string, deque<string>> trip; // 邻接表
  25.     vector<string> route; // 所求路径的倒置
  26.    
  27.     void dfs(const string& src) {
  28.         auto& dests = trip[src];
  29.         while(!dests.empty()) {
  30.             const string dest = dests.front();
  31.             dests.pop_front();
  32.             dfs(dest);
  33.         }
  34.         route.push_back(src);
  35.     }
  36. };
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top