题目
给你一个下标从 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
解题
方法一：回溯（超时）
使用和leetcode-332：重新安排行程类似的方式，进行暴力回溯，但是超时了。
class Solution { public: unordered_map<int,map<vector<int>,int>> targets; bool backtracing(int k,vector<vector<int>>& res){ if(res.size()==k){ return true; } for(pair<const vector<int>,int>& target:targets[res.back()[1]]){ if(target.second>0){ res.push_back(target.first); target.second--; if(backtracing(k,res)) return true; target.second++; res.pop_back(); } } return false; } vector<vector<int>> validArrangement(vector<vector<int>>& pairs) { vector<vector<int>> res; for(const vector<int>& vec:pairs){ targets[vec[0]][vec]++; } for(vector<int>& vec:pairs){ res.push_back(vec); targets[vec[0]][vec]--; if(backtracing(pairs.size(),res)) break; targets[vec[0]][vec]++; res.pop_back(); } return res; } };
方法二：欧拉路径问题（Hierholzer 算法）
无向图中，度指的是一个顶点有多少关联的边
有向图中，度可以分为入度和出度
这道题是一道有向图
因为每一条线都是有方向的,所以称之为有向图
直接记录边
class Solution { public: unordered_map<int,vector<int>> map; unordered_map<int,int> deg; vector<vector<int>> res; void dfs(int curr){ while(map.count(curr)&&!map[curr].empty()){ int tmp=map[curr].back(); map[curr].pop_back(); dfs(tmp); res.push_back({curr,tmp}); } } vector<vector<int>> validArrangement(vector<vector<int>>& pairs) { for(vector<int>& pair:pairs){ map[pair[0]].push_back(pair[1]); deg[pair[0]]--,deg[pair[1]]++; } for(auto it=deg.begin();it!=deg.end();it++) if(it->second==-1) dfs(it->first); if(res.empty()) dfs(deg.begin()->first); reverse(res.begin(),res.end()); return res; } };
同样可以记录节点
class Solution { public: unordered_map<int,vector<int>> map; unordered_map<int,int> deg; vector<int> res; void dfs(int curr){ while(map.count(curr)&&!map[curr].empty()){ int tmp=map[curr].back(); map[curr].pop_back(); dfs(tmp); } res.push_back(curr); } vector<vector<int>> validArrangement(vector<vector<int>>& pairs) { for(vector<int>& pair:pairs){ map[pair[0]].push_back(pair[1]); deg[pair[0]]--,deg[pair[1]]++; } for(auto it=deg.begin();it!=deg.end();it++) if(it->second==-1) dfs(it->first); if(res.empty()) dfs(deg.begin()->first); reverse(res.begin(),res.end()); vector<vector<int>> ans; for(int i=1;i<res.size();i++){ ans.push_back({res[i-1],res[i]}); } return ans; } };
