欧拉回路与欧拉路径实例分析

我们先来看题目描述：

给你一个下标从 开始的二维整数数组 pairs，其中 pairs[i] = [starti, endi]。如果 pairs 的一个重新排列，满足对每一个下标 i（1 <= i < pairs.length）都有 endi-1 == starti，那么我们就认为这个重新排列是 pairs 的一个合法重新排列。 请你返回任意一个 pairs 的合法重新排列。 注意：数据保证至少存在一个 pairs 的合法重新排列。

• 1 <= pairs.length <= 105
• 0 <= starti, endi <= 109

读者可能会尝试把每个 pair 看作一个点，并在所有 end 和 start 相等的 pair 之间连一条有向边。然而，设 pair 的数量有 个，这样构建的图将有 条边（考虑 个 pair 满足 end == 1，另外 个 pair 满足 start == 1 的数据），无法满足本题的数据范围。并且，读者还需要在这样构建的图中找出一条经过所有点恰好一次的路径（即哈密顿路径^12），这是一个 NP 完全问题，同样无法满足本题的数据范围。

上述建图的方式没有较好地利用 endi-1 == starti 的性质。我们反过来将 start 和 end 看作点，将每个 pair 看作从 start 指向 end 的有向边。这样建图自然保证了连续走过的两条边满足 endi-1 == starti。更妙的是，我们只需要找到一条经过所有边恰好一次的路径，又回到了我们熟悉的有向图的欧拉路径问题。

由于题目保证有解（即保证存在欧拉路径），我们可以省去大量判断，直接使用 Hierholzer 算法即可。本题的 C++ 代码如下：

class Solution { public: vector<vector<int>> validArrangement(vector<vector<int>>& pairs) { // 构建有向图 unordered_map<int, vector<int>> e; unordered_map<int, int> inDeg, outDeg; for (auto &p : pairs) { e[p[0]].push_back(p[1]); outDeg[p[0]]++; inDeg[p[1]]++; } int s = -1; // 入度比出度少 1 的节点就是起点 for (auto &p : e) if (inDeg[p.first] + 1 == outDeg[p.first]) s = p.first; // 如果起点未指定，说明存在欧拉回路，选择任意一个非零度节点即可 if (s == -1) s = pairs[0][0]; vector<vector<int>> ans; function<void(int)> dfs = [&](int sn) { while (e[sn].size() > 0) { int fn = e[sn].back(); // 删除有向边 sn -> fn e[sn].pop_back(); // 继续遍历相邻点 dfs(fn); // 将有向边 sn -> fn 加入结果序列中 ans.push_back({sn, fn}); } }; dfs(s); // ans 保存的是欧拉路径的倒序，必须 reverse 才是正确答案 reverse(ans.begin(), ans.end()); return ans; } };