leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

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