我们先来看题目描述：

给你一个下标从 开始的二维整数数组 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;
    }
};