leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

2097.cpp (1034B)

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 };