# 23ms solution using adjacency matrix

• ``````class Solution {
public:
unordered_map<string, int> _cityIdxMap;
vector<string> _cityVec;

bool dfs(vector<vector<int>> &flights, int nRest, int from, vector<string> &ans)
{
ans.push_back( _cityVec[from] );
if(nRest == 0) return true;
for(int t=0; t<_cityVec.size(); ++t) {
if(flights[from][t] > 0) {
flights[from][t]--;
if(dfs(flights, nRest-1, t, ans)) return true;
flights[from][t]++;
}
}
ans.pop_back();
return false;
}

vector<string> findItinerary(vector<pair<string, string>> tickets) {
for( const auto &flight : tickets) {
_cityIdxMap[flight.first] = 0;
_cityIdxMap[flight.second] = 0;
}
for(const auto &cityIdx : _cityIdxMap) {
_cityVec.push_back(cityIdx.first);
}
sort(_cityVec.begin(), _cityVec.end());
for(int i=0; i<_cityVec.size(); ++i) {
_cityIdxMap[ _cityVec[i] ] = i;
}

vector<vector<int>> flights(_cityVec.size(), vector<int>(_cityVec.size(), 0));
for(const auto &t : tickets) {
int fromIdx = _cityIdxMap[ t.first ];
int toIdx = _cityIdxMap[ t.second ];
flights[fromIdx][toIdx]++;
}
vector<string> ans;
dfs(flights, tickets.size(), _cityIdxMap["JFK"], ans);
return ans;
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.