leetcode

0 class Solution {

1 public:

2 vector<vector<int>> validArrangement(const vector<vector<int>> &pairs) const {

3 unordered_map<int, int> in, out, count;

4 unordered_map<int, vector<int>> adj;

5

6 for (const auto &p : pairs) {

7 adj[p[0]].push_back(p[1]);

8 out[p[0]]++, in[p[1]]++;

9 }

10

11 int start = pairs[0][0];

12 for (const auto &[v, _] : adj) {

13 if (out[v] - in[v] != 1) continue;

14 start = v;

15 break;

16 }

17

18 stack<int> st;

19 vector<int> res;

20 for (st.push(start); !st.empty();) {

21 const int crnt = st.top();

22

23 if (count[crnt] != size(adj[crnt])) {

24 st.push(adj[crnt][count[crnt]++]);

25 } else {

26 res.push_back(crnt);

27 st.pop();

28 }

29 }

30

31 vector<vector<int>> pair_res;

32 for (int i = size(res) - 2; i >= 0; i--) {

33 pair_res.push_back({res[i + 1], res[i]});

34 }

35

36 return pair_res;

37 }

38 };