fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. class Solution {
  5. private:
  6.     unordered_map<string, vector<string>> graph;
  7.  
  8.     // city -> longest path length starting from city
  9.     unordered_map<string, int> dp;
  10.  
  11.     // city -> next city in longest path
  12.     unordered_map<string, string> nextCity;
  13.  
  14.     int dfs(string city) {
  15.         if (dp.count(city))
  16.             return dp[city];
  17.  
  18.         int maxLen = 1; // city itself
  19.  
  20.         for (auto &nbr : graph[city]) {
  21.             int currLen = 1 + dfs(nbr);
  22.  
  23.             if (currLen > maxLen) {
  24.                 maxLen = currLen;
  25.                 nextCity[city] = nbr;
  26.             }
  27.         }
  28.  
  29.         return dp[city] = maxLen;
  30.     }
  31.  
  32. public:
  33.     vector<string> longestItinerary(
  34.         vector<pair<string, string>>& routes) {
  35.  
  36.         unordered_set<string> allCities;
  37.  
  38.         for (auto &route : routes) {
  39.             string from = route.first;
  40.             string to = route.second;
  41.  
  42.             graph[from].push_back(to);
  43.  
  44.             allCities.insert(from);
  45.             allCities.insert(to);
  46.         }
  47.  
  48.         string startCity;
  49.         int longestLength = 0;
  50.  
  51.         for (auto &city : allCities) {
  52.             int len = dfs(city);
  53.  
  54.             if (len > longestLength) {
  55.                 longestLength = len;
  56.                 startCity = city;
  57.             }
  58.         }
  59.  
  60.         vector<string> path;
  61.  
  62.         while (!startCity.empty()) {
  63.             path.push_back(startCity);
  64.  
  65.             if (!nextCity.count(startCity))
  66.                 break;
  67.  
  68.             startCity = nextCity[startCity];
  69.         }
  70.  
  71.         return path;
  72.     }
  73. };
  74.  
  75. int main() {
  76.     vector<pair<string, string>> routes = {
  77.         {"Chennai", "Hyderabad"},
  78.         {"Hyderabad", "Bangalore"},
  79.         {"Bangalore", "Delhi"},
  80.         {"Hyderabad", "Delhi"}
  81.     };
  82.  
  83.     Solution obj;
  84.  
  85.     vector<string> ans = obj.longestItinerary(routes);
  86.  
  87.     for (int i = 0; i < ans.size(); i++) {
  88.         cout << ans[i];
  89.  
  90.         if (i != ans.size() - 1)
  91.             cout << " -> ";
  92.     }
  93.  
  94.     cout << endl;
  95.  
  96.     return 0;
  97. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Chennai -> Hyderabad -> Bangalore -> Delhi
https://ideone.com/FnPYFq
language:
C++ (gcc 8.3)
created:
9 hours 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!