Description

Submission

class Solution {
    vector<string> rets;
    unordered_map<string, multiset<string>> graph;

    void dfs(string cur) {
        while(graph.count(cur) && !graph[cur].empty()) {
            string tmp = *graph[cur].begin();
            graph[cur].erase(graph[cur].begin());
            dfs(tmp);
        }
        rets.push_back(cur);
    }
public:
    vector<string> findItinerary(vector<vector<string>>& tickets) {
        for(auto& ticket: tickets) {
            graph[ticket[0]].insert(ticket[1]);
        }

        dfs("JFK");
        reverse(rets.begin(), rets.end());
        return rets;
    }
};

// find all the cycles at each vertex