leetcode332

Hierholzer算法
https://taodaling.github.io/blog/2019/04/25/Hierholzer%E7%AE%97%E6%B3%95/
https://www.cnblogs.com/vocaloid01/p/9514023.html
https://www.jianshu.com/p/8394b8e5b878

332方法1dfs

class Solution {
public:
    vector<string> findItinerary(vector<vector<string>>& tickets) {
        vector<string> ret;
        unordered_map<string,multiset<string>> graph=buildGraph(tickets);
        string jfk = "JFK";
        //cout<<typeid(jfk).name()<<endl; 
        //stdout：NSt7__cxx1112basic_stringIcSt11char_traitsIcESaIcEEE
        //cout<<typeid("JFK").name()<<endl;
        //stdout：A4_c
        //dfs(graph,"JFK",ret);报错no matching member function for call to 'dfs'
        dfs(graph,jfk,ret);
        return vector<string>(ret.rbegin(),ret.rend());
    }
    private:
    //typedef vector<string,multiset<string>> Graph;
    template <typename T>
    unordered_map<T,multiset<T>> buildGraph(vector<vector<T>>& tickets) {
        unordered_map<T,multiset<T>> g;
        for(auto ticket:tickets){
            g[ticket[0]].insert(ticket[1]);
        }
        return g;
    }
    template <typename T>
    void dfs(unordered_map<T,multiset<T>>& _graph,T _t,vector<T>& _ret){
        while(_graph[_t].size()){
            T t=*_graph[_t].begin();
            _graph[_t].erase(_graph[_t].begin());
            dfs(_graph,t,_ret);
        }
        _ret.push_back(_t);
    }
};

332方法2while

class Solution {
public:
    vector<string> findItinerary(vector<vector<string>>& tickets) {
        vector<string> ret;
        unordered_map<string,multiset<string>> graph=buildGraph(tickets);
        stack<string> sta{{"JFK"}};
        while(!sta.empty()){
            string tmp=sta.top();
            if(graph[tmp].empty()){
                ret.insert(ret.begin(), tmp);
                sta.pop();
                
            }else{
                sta.push(*graph[tmp].begin());
                graph[tmp].erase(graph[tmp].begin());
            }
            
        }
        return ret;
    }
    private:
    template <typename T>
    unordered_map<T,multiset<T>> buildGraph(vector<vector<T>>& tickets) {
        unordered_map<T,multiset<T>> g;
        for(auto ticket:tickets){
            g[ticket[0]].insert(ticket[1]);
        }
        return g;
    }
};