# Could anybody show me how to consider the time complexity of this kind of code?

• In this question, I used a map<string, set<string>> to record each flight and do dfs & backtracking.

However, the size of each set is not fixed. What's the right way to think about the time complexity?

Here is my code.

``````class Solution {
public:
bool dfs(unordered_map<string, set<string>> &graph, vector<string> &res, int count, string depart) {
// Get all tickets.
if (count == 0) return true;
// No more tickets at current location.
else if (graph[depart].size() == 0) return false;
else {
set<string>::iterator lastIter, curIter = graph[depart].begin();
while (curIter != graph[depart].end()) {
string temp = *curIter;
lastIter = curIter++;
// We need erase the choice of arrival then add it back after dfs.
graph[depart].erase(lastIter);
if (dfs(graph, res, count - 1, temp)) {
res.push_back(temp);
return true;
}
graph[depart].insert(temp);
}
return false;
}
}
vector<string> findItinerary(vector<pair<string, string>> tickets) {
vector<string> res;
if (tickets.size() != 0) {
// Build the graph, use set to sort the arrivals.
unordered_map<string, set<string>> graph;
for (auto t:tickets) {
graph[t.first].insert(t.second);
}
if (dfs(graph, res, tickets.size(), "JFK")) {
res.push_back("JFK");
reverse(res.begin(), res.end());
}
}
return res;
}
};``````

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