1
class Solution {
2
 public:
3
  vector<vector<int>> validArrangement(vector<vector<int>> &pairs) {
4
    int m = pairs.size();
5
    // Eulerian Path
6
    unordered_map<int, stack<int>> adj;
7
    unordered_map<int, int> in;
8
    unordered_map<int, int> out;
9
    // reserve spaces for unordered_map may help in runtime.
10
    adj.reserve(m);
11
    in.reserve(m);
12
    out.reserve(m);
13
    for (int i = 0; i < m; i++) {
14
      int u = pairs[i][0], v = pairs[i][1];
15
      in[v]++;
16
      out[u]++;
17
      adj[u].push(v);
18
    }
19
    // find the starting node
20
    int start = -1;
21
    for (auto &p : adj) {
22
      int i = p.first;
23
      if (out[i] - in[i] == 1) start = i;
24
    }
25
    if (start == -1) {
26
      // Eulerian Circuit -> start at any node
27
      start = adj.begin()->first;
28
    }
29
    vector<vector<int>> ans;
30
    euler(adj, ans, start);
31
    reverse(ans.begin(), ans.end());
32
    return ans;
33
  }
34

35
 private:
36
  void euler(unordered_map<int, stack<int>> &adj, vector<vector<int>> &ans, int curr) {
37
    auto &stk = adj[curr];
38
    while (!stk.empty()) {
39
      int nei = stk.top();
40
      stk.pop();
41
      euler(adj, ans, nei);
42
      // postorder
43
      ans.push_back({curr, nei});
44
    }
45
  }
46
};