LeetCode 332 Reconstruct Itinerary

给定连通图的一些边，问如何不重复走边遍历完这个图，并且边有一个名字，要使名字的字典序最小

想到用dfs来直接搜索，但是这题存在有环的问题，即一个节点会被遍历多次。如果采用至上而下的搜索，则会产生很多没用的搜索和回溯。可以采用至下而上的搜索策略，即如果一个所有的出度都被搜索过了，那么就可以入队。这样第一个入队的一定是终点。如果一个点有多个出度，即一个环的入口，那么只要用一个multiset来保证搜索出度是按照字典序就可以。

C++ Code

class Solution {
public:
    void dfs(map<string, multiset<string>> &mp, string cur, vector<string> &result) {
        while(mp[cur].size()) {
            string nex = *(mp[cur].begin());
            mp[cur].erase(mp[cur].begin());
            dfs(mp, nex, result);
        }
        result.push_back(cur);
    }
    
    vector<string> findItinerary(vector<vector<string>>& tickets) {
        map<string, multiset<string>> mp;
        for(auto item: tickets) {
            mp[item[0]].insert(item[1]);
        }
        string cur = "JFK";
        vector<string> result;
        dfs(mp, cur, result);
        reverse(result.begin(), result.end());
        return result;
    }
};