332. Reconstruct Itinerary

基于dfs的类拓扑排序（不是真的拓扑排序） O(n) time O(n) space
后序遍历，当一个节点的所有子节点都被遍历过之后，将该节点加入，因为是倒序，所有最后要翻转过来，因为是类似拓扑排序，所以出度为0的末端点（最多一个）即便最先被访问也是第一个入栈，要排在最后
如果没有出度为0的点，前序遍历也是可以的，但是出度为0的点没有子节点所以必须最后访问，只有栈+后序遍历才能做到

class Solution {
public:
    vector<string> findItinerary(vector<vector<string>>& tickets) {
        if (tickets.empty()) return {};
        for (const auto &e : tickets) {
            g[e[0]].insert(e[1]);
        }
        dfs("JFK");
        return vector<string>(rbegin(res), rend(res));
    }

    void dfs(const string &u) {
        while (!g[u].empty()) {
            auto it = begin(g[u]);
            auto v = *it;
            g[u].erase(it); // 删除以避免重复访问
            dfs(v);
        }
        res.push_back(u);
    }

    vector<string> res;
    unordered_map<string, multiset<string>> g; // 因为需要字典序所以要用set，因为一个起点可以多次去一个中点所以要用multiset
};