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

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 向量中；但我无法理解 if condition:

背后的直觉

如何只在集合为空时才出栈，保证这个测试用例得到处理？

Answer 1

在访问了一个 to 城市后，它被删除了，这实际上意味着 to 城市作为一个中间 from 城市已经访问过，下次不需要考虑相应的from 城市被访问，否则它将是一个没有停止条件的永无止境的循环。

因此 if 语句用于检查 from 城市的所有 to 城市是否已经访问过。它几乎就像一个访问过的数组，跟踪到目前为止访问过的所有城市。

Answer 2

问题本质上是在有向图中找到 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.

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

P.S。虽然算法很简单，但正确性的证明并不是那么简单。有兴趣的可以上网搜索一下。

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

Intuition behind popping the values only when the set is empty

c++

algorithm

graph

graph-traversal