[数据结构与算法]欧拉通路—合法重新排列数对（leetcode 2097）

题目描述

给你一个下标从 0?开始的二维整数数组?pairs?，其中?pairs[i] = [starti, endi]?。如果 pairs?的一个重新排列，满足对每一个下标 i （?1 <= i < pairs.length?）都有?endi-1 == starti ，那么我们就认为这个重新排列是?pairs 的一个 合法重新排列 。

请你返回 任意一个?pairs 的合法重新排列。

注意：数据保证至少存在一个 pairs?的合法重新排列。

示例 1：

输入：pairs = [[5,1],[4,5],[11,9],[9,4]]
输出：[[11,9],[9,4],[4,5],[5,1]]
解释：
输出的是一个合法重新排列，因为每一个 endi-1 都等于 starti?。
end0 = 9 == 9 = start1?
end1 = 4 == 4 = start2
end2 = 5 == 5 = start3
示例 2：

输入：pairs = [[1,3],[3,2],[2,1]]
输出：[[1,3],[3,2],[2,1]]
解释：
输出的是一个合法重新排列，因为每一个 endi-1 都等于 starti?。
end0 = 3 == 3 = start1
end1 = 2 == 2 = start2
重新排列后的数组 [[2,1],[1,3],[3,2]] 和 [[3,2],[2,1],[1,3]] 都是合法的。
示例 3：

输入：pairs = [[1,2],[1,3],[2,1]]
输出：[[1,2],[2,1],[1,3]]
解释：
输出的是一个合法重新排列，因为每一个 endi-1 都等于 starti?。
end0 = 2 == 2 = start1
end1 = 1 == 1 = start2
?

提示：

1 <= pairs.length <= 105
pairs[i].length == 2
0 <= starti, endi <= 109
starti != endi
pairs?中不存在一模一样的数对。
至少 存在 一个合法的?pairs?重新排列。

问题分析

方法一：有向图的欧拉通路

欧拉通路的起始节点：

1、如果图中所有节点的入度和出度都相等，那么从任意节点开始都存在欧拉通路；

2、如果图中存在一个节点的出度比入度恰好多 1，另一个节点的入度恰好比出度多 1，那么欧拉通路必须从前一个节点开始，到后一个节点结束。

3、除此之外的有向图都不存在欧拉通路，

本体保证了至少存在一个合法排列，因此图已经是上述的两种情况之一。

Hierholzer 算法流程如下：

从起点出发，进行深度优先搜索。
每次沿着某条边从某个顶点移动到另外一个顶点的时候，都需要删除这条边（灵魂）。
如果没有可移动的路径，则将所在节点加入到结果中，并返回。
当我们顺序地考虑该问题时，我们也许很难解决该问题，因为我们无法判断当前节点的哪一个分支是「死胡同」分支。

不妨倒过来思考。我们注意到只有那个入度与出度差为 1 的节点会导致死胡同。而该节点必然是最后一个遍历到的节点。我们可以改变记录的规则，当我们遍历完一个节点所连的所有节点后，我们才将该节点记录（即逆序）。

对于当前节点而言，从它的每一个非「死胡同」分支出发进行深度优先搜索，都将会搜回到当前节点。

而从它的「死胡同」分支出发进行深度优先搜索将不会搜回到当前节点。

也就是说当前节点的死胡同分支将会优先于其他非「死胡同」分支记录。

这样就能保证我们可以「一笔画」地走完所有边，最终的记录结果逆序地保存了「一笔画」的结果。我们只要将结果中的内容反转，即可得到答案。

模版有四步：

建邻接表、入度表、出度表
根据是通路还是回路判断是否要找起点start
Hierholzer 算法找路
最后将上一步找的路再逆回来

代码

class Solution {
public:
    unordered_map<int, int> in, out;
    unordered_map<int, vector<int>> edges;
    vector<vector<int>> ans;

    void dfs(int n) {
        while(!edges[n].empty()) {
            int v = edges[n].back();
            edges[n].pop_back();
            dfs(v);
            ans.push_back({n, v});
        }
    }

    vector<vector<int>> validArrangement(vector<vector<int>>& pairs) {

        for(const auto& e:pairs) {
            edges[e[0]].push_back(e[1]);
            in[e[1]]++;
            out[e[0]]++;
        }

        // 如果是存在出度比入度多一个的则从匹配到的点为起始点，
        // 如果不存在，则为入度==出度情况，从任意点都可以，此处默认从pairs[0][0]为起始点。
        int start = pairs[0][0];
        // 寻找起始点只能遍历 out集合，in集合在起始点入度为0的情况下得不到统计
        for (const auto& [x, outdu]: out) {
            // 如果有节点出度比入度恰好多 1，那么只有它才能是起始节点
            if (outdu == in[x] + 1) {
                start = x;
                break;
            }
        }

        dfs(start);
        reverse(ans.begin(), ans.end());
        return ans;
    }
};

复杂度分析

时间复杂度：O(n)，其中 n?是数组pairs?的长度。图中有不超过 n+1?个节点和 n?条边，因此求解欧拉通路需要的时间为 O(n)。

空间复杂度：O(n)，即为存储图需要使用的空间。