leetcode2097 合法重新排列数对

思路：

有向图求欧拉通路，使用Hierholzer算法求解。

实现：

 1 class Solution
 2 {
 3 public:
 4     void dfs(int x, vectorint>>& g, vector<int>& trace)
 5     {
 6         while (!g[x].empty())
 7         {
 8             int to = g[x].back();
 9             g[x].pop_back();
10             dfs(to, g, trace);
11         }
12         trace.push_back(x);
13     }
14     vectorint>> validArrangement(vectorint>>& pairs)
15     {
16         int n = pairs.size();
17         unordered_map<int, int> mp;
18         for (int i = 0; i < n; i++)
19         {
20             int x = pairs[i][0], y = pairs[i][1];
21             if (!mp.count(x)) mp[x] = mp.size();
22             if (!mp.count(y)) mp[y] = mp.size();
23         }
24         unordered_map<int, int> mp_rev;
25         for (auto it: mp) mp_rev[it.second] = it.first;
26         int m = mp.size();
27         vectorint>> g(m, deque<int>());
28         vector<int> ind(m, 0), outd(m, 0);
29         for (int i = 0; i < n; i++)
30         {
31             int x = pairs[i][0], y = pairs[i][1];
32             x = mp[x]; y = mp[y];
33             outd[x]++; ind[y]++;
34             g[x].push_back(y);
35         }
36         int start = -1;
37         for (int i = 0; i < m; i++)
38         {
39             if (outd[i] == ind[i] + 1) { start = i; break; }
40         }
41         if (start == -1) start = 0;
42         vector<int> trace;
43         dfs(start, g, trace);
44         reverse(trace.begin(), trace.end());
45         vectorint>> res;
46         for (int i = 0; i < trace.size() - 1; i++)
47         {
48             res.push_back(vector<int>{mp_rev[trace[i]], mp_rev[trace[i + 1]]});
49         }
50         return res;
51     }
52 };