leetcode

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

2392.cpp (1411B)

      1 class Solution {
      2     static vector<int> create(int k, const vector<vector<int>> &conditions) {
      3         vector<vector<int>> adj(k + 1);
      4         static int count[402];
      5 
      6         memset(count, 0x00, sizeof(count));
      7         for (const auto &row : conditions) {
      8             adj[row[0]].push_back(row[1]);
      9             count[row[1]]++;
     10         }
     11 
     12         queue<int> q;
     13         for (int i = 1; i <= k; i++) {
     14             if (count[i] != 0) continue;
     15             q.push(i);
     16         }
     17 
     18         if (q.empty()) return {};
     19 
     20         int cnt = 0;
     21         vector<int> res(k + 1, -1);
     22         while (!q.empty()) {
     23             const auto crnt = q.front();
     24             q.pop();
     25 
     26             for (const int below : adj[crnt]) {
     27                 if (--count[below] != 0) continue;
     28                 q.push(below);
     29             }
     30 
     31             res[crnt] = cnt++;
     32         }
     33 
     34         return cnt == k ? res : vector<int>();
     35     }
     36 
     37   public:
     38     vector<vector<int>> buildMatrix(int k, const vector<vector<int>> &rowConditions,
     39                                     const vector<vector<int>> &colConditions) const {
     40         const auto row = create(k, rowConditions);
     41         if (row.empty()) return {};
     42 
     43         const auto col = create(k, colConditions);
     44         if (col.empty()) return {};
     45 
     46         vector<vector<int>> res(k, vector(k, 0));
     47         for (int i = 1; i <= k; i++)
     48             res[row[i]][col[i]] = i;
     49 
     50         return res;
     51     }
     52 };