LeetCode 2097. 合法重新排列数对（欧拉路径）

示例 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 <= 10^5
pairs[i].length == 2
0 <= starti, endi <= 10^9
starti != endi
pairs 中不存在一模一样的数对。
至少 存在 一个合法的 pairs 重新排列。

class Solution {
    vector<int> path;
public:
    vector<vector<int>> validArrangement(vector<vector<int>>& pairs) {
        int n = pairs.size();
        unordered_map<int, multiset<int>> g; //图
        unordered_map<int, int> indegree, outdegree;
        for(int i = 0; i < n; ++i)
        {
            int x = pairs[i][0], y = pairs[i][1];
            outdegree[x]++;
            indegree[y]++;
            g[x].insert(y);
        }
        int start = pairs[0][0];
        for(int i = 0; i < n; ++i)
        {
            int x = pairs[i][0], y = pairs[i][1];
            int indegree_i = indegree.count(x) ? indegree[x] : 0;
            int outdegree_i = outdegree.count(x) ? outdegree[x] : 0;
            if(indegree_i + 1 == outdegree_i)
            {
                start = x;
                break;
            }
        }
        dfs(start, g);
        vector<vector<int>> ans;
        for(int i = path.size()-1; i > 0; i--) // 逆序输出就是欧拉路径
            ans.push_back({path[i], path[i-1]});
        return ans;
    }
    void dfs(int idx, unordered_map<int, multiset<int>>& g)
    {
        while(g[idx].size())
        {
            int nt = *g[idx].begin();
            g[idx].erase(g[idx].begin());
            dfs(nt, g);
        }
        path.push_back(idx);
    }
};