# 32ms sort and dfs solution

• Build a graph to record city list which can be reached from one city, and the list will be sorted, so that we got the smallest lexical order path.

``````//path got when getting ori
//if find the answer return true
bool dfs(vector<string>& path, int curTic, int totalTic, const string& ori, unordered_map<string, vector<pair<string, bool>>>& linkMap)
{
if(curTic == totalTic)
{
return true;
}
{
vector<pair<string, bool>> &nei = linkMap[ori];
for(int i = 0; i < nei.size(); i++)
{
if(!nei[i].second)  //if not visited
{
path.push_back(nei[i].first);
nei[i].second = true;
if(dfs(path, curTic + 1, totalTic, nei[i].first, linkMap))
{
return true;
}
path.pop_back();
nei[i].second = false;
}
}
}
return false;
}

class Solution
{
public:
vector<string> findItinerary(vector<pair<string, string>> tickets)
{
unordered_map<string, vector<pair<string, bool>>> linkMap;
for(int i = 0; i < tickets.size(); i++)
{
}
for(auto it = linkMap.begin(); it != linkMap.end(); it++)
{
sort(it->second.begin(), it->second.end());
}
vector<string> path;
path.push_back("JFK");
dfs(path, 0, tickets.size(), "JFK", linkMap);
return path;
}
};``````

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