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

我正在解决有关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 。但是如果满足以下条件，我将无法理解其背后的直觉:

仅当集合为空时如何从堆栈中弹出，以确保该测试用例得到妥善处理？

最佳答案

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

投票赞成的答案使用一种称为Hierholzer's algorithm的算法(Hierholzer的算法最初用于查找欧拉循环，但是很容易针对欧拉路径进行修改)。通常，它



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

附言尽管算法很简单，但是正确性的证明并不是那么简单。如果您对此感兴趣，可以在Internet上进行搜索。