fork download
copy 
  1. #include <iostream>
  2. #include <unordered_set>
  3. #include <unordered_map>
  4. #include <vector>
  5. #include <string>
  6. using namespace std;
  7.  
  8. class Solution {
  9. public:
  10.     vector<string> findItinerary(vector<vector<string>>& tickets) {
  11.         unordered_set<string> cities;
  12.         for (const auto& flight : tickets)
  13.         {
  14.             for (const auto& city : flight)
  15.             {
  16.                 if (cities.count(city) > 0)
  17.                     cities.erase(city);
  18.                 else
  19.                     cities.insert(city);
  20.             }
  21.         }
  22.  
  23.         unordered_map<string, pair<string, string>> data;
  24.         for (const auto& flight : tickets)
  25.         {
  26.             const auto& city1 = flight[1];
  27.             const auto& city2 = flight[2];
  28.             if (0 == data.count(city1))
  29.             {
  30.                 if (data[city1].first.empty())
  31.                     data[city1].first = city2;
  32.                 else
  33.                     data[city1].second = city2;
  34.             }
  35.             if (0 == data.count(city2))
  36.             {
  37.                 if (data[city2].first.empty())
  38.                     data[city2].first = city1;
  39.                 else
  40.                     data[city2].second = city1;
  41.             }
  42.         }
  43.  
  44.         vector<string> result;
  45.  
  46.         auto city = *cities.begin();
  47.         auto cityLast = *(++cities.begin());
  48.  
  49.         unordered_set<string> visited;
  50.         while (city != cityLast)
  51.         {
  52.             result.push_back(city);
  53.             visited.insert(city);
  54.  
  55.             if (visited.count(data[city].first) > 0)
  56.                 city = data[city].second;
  57.             else
  58.                 city = data[city].first;
  59.         }
  60.         result.push_back(city);
  61.  
  62.         return result;
  63.     }
  64. };
  65.  
  66. int main() {
  67. 	// your code goes here
  68. 	return 0;
  69. }
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/iDR0Eo
language:
C++14 (gcc 8.3)
created:
11 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!