leetcode 2097. 合法重新排列数对

 //这是一道一笔画问题
  算法名字叫Hierholzer 算法
  算法介绍传送门https://www.cnblogs.com/acxblog/p/7390301.html
1 class Solution { 2 public: 3 vector<vector<int>> validArrangement(vector<vector<int>>& pairs) { 4 vector<vector<int>>ans; 5 map<int,vector<int>>G; 6 map<int,int>du; 7 for(auto &p:pairs) 8 { 9 G[p[0]].push_back(p[1]); 10 du[p[0]]--; 11 du[p[1]]++; 12 } 13 int st=du.begin()->first; 14 for(auto &p:du)if(p.second==-1){st=p.first;break;} 15 function<void(int)>dfs=[&](int u)//dfs(v)表示获得v开始的欧拉回路或者欧拉路; 16 { 17 vector<int>&e=G[u]; 18 while(e.size()) 19 { 20 int v=e.back(); 21 e.pop_back();//由欧拉路的性质,每条边只被访问一次,如果不是访问一次,子问题会重复; 22 dfs(v); 23 ans.push_back({u,v});//因为是push_back,我们的结果只能是逆序,我们把结果加进去 24 } 25 }; 26 dfs(st);//万物皆可DP 27 reverse(ans.begin(),ans.end()); 28 return ans; 29 } 30 };

 

上一篇:多重全排列的生成与构造算法


下一篇:[模板] map