c++ - 仅当集合为空时才弹出值的直觉

Question

我正在解决 Leetcode 上的一个问题:https://leetcode.com/problems/reconstruct-itinerary/description/ .问题是:

Given a list of airline tickets represented by pairs of departure and 
arrival airports [from, to], reconstruct the itinerary in order. All of 
the tickets belong to a man who departs from JFK. Thus, the itinerary 
must begin with JFK.

例如，如果 tickets = [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO "]]，输出应该是:["JFK", "MUC", "LHR", "SFO", "SJC"]。

我写了下面的代码，它(可以理解)在输入时中断 [["JFK","KUL"],["JFK","NRT"],["NRT","JFK"] ]，因为根据我的代码，节点“NRT”仍未被访问:

class Solution {
public:
    vector<string> findItinerary(vector<pair<string, string>> tickets) {
        if(tickets.empty()) return vector<string>();

        vector<string> result;
        unordered_map<string, multiset<string>> itinerary;

        for(auto& each : tickets)
            itinerary[each.first].insert(each.second);

        stack<string> myStack;
        myStack.push("JFK");
        while(!myStack.empty()) {
            string topVal=myStack.top();
            result.push_back(topVal);
            myStack.pop();
            if(!itinerary[topVal].empty()) {
                myStack.push(*itinerary[topVal].begin());
                itinerary[topVal].erase(itinerary[topVal].begin());
            }
        }

        return result;
    }
};

为了克服这个问题，其中一个被赞成的解决方案提出了这个小改动:

class Solution {
public:
    vector<string> findItinerary(vector<pair<string, string>> tickets) {
        if(tickets.empty()) return vector<string>();

        vector<string> result;
        unordered_map<string, multiset<string>> itinerary;

        for(auto& each : tickets)
            itinerary[each.first].insert(each.second);

        stack<string> myStack;
        myStack.push("JFK");
        while(!myStack.empty()) {
            string topVal=myStack.top();
            if(itinerary[topVal].empty()) {   //--->this if condition
                result.push_back(topVal);
                myStack.pop();
            }
            else {
                myStack.push(*itinerary[topVal].begin());
                itinerary[topVal].erase(itinerary[topVal].begin());
            }
        }

        reverse(result.begin(), result.end());
        return result;
    }
};

现在，我使用示例 [["JFK","KUL"],["JFK","NRT"],["NRT","JFK"]]，并了解它如何以相反的方式将值插入到 result vector 中；但我无法理解 if 条件背后的直觉:

如何仅在集合为空时才从堆栈中弹出，确保处理此测试用例？

Answer 1

问题本质上是找到一个 Eulerian path在有向图中，每个 [from, to] 对代表一条边。

赞成的答案使用了一种名为 Hierholzer's algorithm 的算法(Hierholzer 算法最初用于寻找欧拉圈，但很容易修改为欧拉路径)。一般来说，

keep following unused edges and removing them until we get stuck. Once we get stuck, we back-track to the nearest vertex in our current path that has unused edges, and we repeat the process until all the edges have been used.

强调的部分是您的解决方案与赞成的解决方案之间的区别。

附言虽然算法很简单，但正确性的证明并不是那么简单。感兴趣的可以上网搜索。