[LeetCode]Reconstruct Itinerary

把每个机场看做顶点，每个ticket看做一条边，题目可以等价于，从JFK出发，保证每一条边只遍历一次并且所有边都可以经过。也就是欧拉路径/一笔画问题。
题目保证了从JFK出发一定有解，也就是一定有欧拉路径的存在。但是为了更全面地理解问题，在我们讲解如何寻找欧拉路径之前，我们需要知道什么样的图含有欧拉路径。我们首先讨论无向图的情况，一个连通无向图存在欧拉环/路径（不闭合）的充要条件是（来源维基）：

• 存在欧拉环的充要条件是，每个节点的度数是偶数
• 存在欧拉路径（不闭合）的充要条件是，度数是奇数的节点数为2

我们首先证明欧拉环的情况，首先如果G存在欧拉环，那么随机从节点v开始，欧拉环也在v点结束，那么我们不可能在任何一个节点停住，所以从一条边进入某个节点，就必然从某条边出去，所以所有节点的度数是偶数。那么假设G的所有节点度数都是偶数，我们随机从v点出发，那么当我们第一次回到v时（不可能停在其他点，因为总有边可以出去），所有环上的节点都减去了两条边，所以所有剩下的节点还是偶数度数。那么我们继续从剩下的节点找环知道耗尽所有的边，这些所有的环C互相之间是有公共节点的，因为G本身就是连通的，所以通过公共节点遍历这些环，就可以找到欧拉环。

欧拉路径（不闭合）的情况就是存在欧拉环的图其中两个节点去掉一条边，证明类似，我们在这里不详述。

对于有向图G来说，存在欧拉环/路径（不闭合）的充要条件是：

• 存在欧拉环的充要条件是，G是强连通图，每个点的出度和入度一样
• 存在欧拉路径（不闭合）的充要条件是，G是连通图，其中两个节点，v的出度比入度多1，w的出度比入度少1，其他节点出度入度是一样的

这个和无向图的条件是非常类似的，我们不做过多的证明。

那么知道了图存在欧拉路径的条件，如何寻找欧拉路径呢，一般来讲我们有Fleury's algorithm和Hierholzer's algorithm，算法对有向图和无向图都是一样的。首先是Fleury's algorithm，具体步骤为：

• 如果存在欧拉环，从任意一点开始。否则，如果是无向图的话，从任意一个度数为基数的节点来时；有向图的话，从出度比入度多1的节点开始。
• 如果当前节点只有一条边的话，选择一条边前进并删除这条边。否则，永远避开bridge而选其他的边。
• 当耗尽所有边，算法结束。

首先我们所说的bridge是一条特殊的边，当我们去掉这一条边的时候，图会变得不连通。那么这个算法为什么是正确的呢？我们先证明欧拉环的情况，这个算法可以保证每条边只遍历一次，因为我们访问完就会删掉这条边 。那么我们只要证明这个算法可以访问所有的边即可。对于每个节点来说，最后访问bridge可以保证我们可以再次回到这个节点来访问其他的边。如果只存在一条bridge，这个是可行的，所以我们只需要证明一个节点不可能含有大于等于两条的bridge。假设一个节点存在两条或者以上的bridge，那么我们总会先访问其中一条，那么删除此边后，图会变得不连通，也就是说，我们无法找到一条路径回到回到原来的点，自然也就不可能形成环，这与我们的前提（存在欧拉环）矛盾。所以每个节点最多只有一条bridge，那么这样我们可以访问所有的边。

对于欧拉路径（不闭合）来说，既然欧拉环可以找到，我们去掉一条边，规定好起点终点之后，欧拉路径也可以通过这种方法找到。假设起点为v终点为w，那么当我们加上从w到v的边之后，可以找到从v回到v的欧拉环，那么去掉w到v的边，v是可以找到从v到w的欧拉路径的。

我们如何确定bridge？很简单，我们去掉这条边，之后DFS，如果我们发现不连通了，说明这条边就是bridge。所以这个算法的复杂度是O((V+E)^2)。

我们可以看出Fleury's algorithm的效率不是特别高，Hierholzer's algorithm是一种效率更高的算法，时间复杂度为O(V+E)，具体步骤为：

• 选好起始点（原则同之前），DFS直到无路可走，收录无路可走的节点。
• 从递归依次返回的图中，如果当前节点有其他的路径，我们重复步骤1，知道耗尽所有边

我们也是先证明欧拉环的情况（不闭合路径的情况同理），假设我们从v出发，我们只可能stuck在v，因为其他的节点都是可以有路出去的。我们找到了一个环。从递归返回并收录无路可走的节点，当我们在某个节点c找到一条新路时，我们可以可以找到一条新环，c就是两环的其中一个交点。依次类推，我们可以找到所有的环，共同组成了欧拉环。显然我们是可以visit所有的边的，因为本质上这就是Postorder DFS，既然图是连通的，我们当然可以遍历所有的边。

所以对于这一题，我们只需要建好图，然后用Fleury's algorithm或者Hierholzer's algorithm即可，这里我们实现Hierholzer's algorithm，注意本题两个节点之间可能有多条边，并且有多个欧拉路径的话取lexicographical更小的那个，所以我们用multiset存边，因为它允许duplicates并且本身是sorted的，代码如下：

	class Solution {
	public:
	vector<string> findItinerary(vector<pair<string, string>> tickets) {
	unordered_map<string, multiset<string>> g;
	for(auto& e : tickets)
	g[e.first].insert(e.second);
	vector<string> path;
	dfs(g, path, "JFK");
	reverse(path.begin(), path.end());
	return path;
	}
	private:
	void dfs(unordered_map<string, multiset<string>>& g, vector<string>& path, string curr)
	{
	while(g[curr].size())
	{
	string next = *g[curr].begin();
	g[curr].erase(g[curr].begin());
	dfs(g, path, next);
	}
	path.emplace_back(curr);
	}
	};

view raw Reconstruct Itinerary.cpp hosted with ❤ by GitHub