2097.cpp (1034B)
1 class Solution { 2 public: 3 vector<vector<int>> validArrangement(const vector<vector<int>> &pairs) const { 4 unordered_map<int, int> in, out, count; 5 unordered_map<int, vector<int>> adj; 6 7 for (const auto &p : pairs) { 8 adj[p[0]].push_back(p[1]); 9 out[p[0]]++, in[p[1]]++; 10 } 11 12 int start = pairs[0][0]; 13 for (const auto &[v, _] : adj) { 14 if (out[v] - in[v] != 1) continue; 15 start = v; 16 break; 17 } 18 19 stack<int> st; 20 vector<int> res; 21 for (st.push(start); !st.empty();) { 22 const int crnt = st.top(); 23 24 if (count[crnt] != size(adj[crnt])) { 25 st.push(adj[crnt][count[crnt]++]); 26 } else { 27 res.push_back(crnt); 28 st.pop(); 29 } 30 } 31 32 vector<vector<int>> pair_res; 33 for (int i = size(res) - 2; i >= 0; i--) { 34 pair_res.push_back({res[i + 1], res[i]}); 35 } 36 37 return pair_res; 38 } 39 };