leetcode

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

1601.cpp (703B)

      1 class Solution {
      2     int degree[21] = {0};
      3     int res = 0;
      4 
      5     void rec(const vector<vector<int>> &req, int cur = 0, int cnt = 0, int dirty = 0) {
      6         if (cnt + (req.size() - cur) < res) return;
      7         if (cur == req.size()) {
      8             if (dirty) return;
      9             res = max(res, cnt);
     10             return;
     11         }
     12 
     13         rec(req, cur + 1, cnt, dirty);
     14 
     15         if (degree[req[cur][0]]++ == 0) dirty++;
     16         if (--degree[req[cur][1]] == 0) dirty--;
     17         rec(req, cur + 1, cnt + 1, dirty);
     18         degree[req[cur][0]]--, degree[req[cur][1]]++;
     19     }
     20 
     21   public:
     22     int maximumRequests(int n, const vector<vector<int>> &requests) {
     23         rec(requests);
     24         return res;
     25     }
     26 };