leetcode

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

1203.cpp (1622B)

      1 class Solution {
      2   public:
      3     vector<int> sortItems(int n, int m, vector<int> &group, const vector<vector<int>> &beforeItems) {
      4         for (int &g : group)
      5             if (g == -1) g = m++;
      6 
      7         vector<unordered_set<int>> gadj(m);
      8         vector<vector<int>> adj(n), ordered(m);
      9         vector<int> gcount(m, 0), count(n, 0);
     10         queue<int> q;
     11 
     12         for (int i = 0; i < n; i++) {
     13             count[i] = beforeItems[i].size();
     14             for (int elem : beforeItems[i]) {
     15                 adj[elem].push_back(i);
     16                 if (group[elem] == group[i]) continue;
     17                 if (gadj[group[elem]].count(group[i])) continue;
     18                 gadj[group[elem]].insert(group[i]);
     19                 gcount[group[i]]++;
     20             }
     21         }
     22 
     23         int cnt = 0;
     24         for (int i = 0; i < n; i++)
     25             if (!count[i]) q.push(i);
     26         while (!q.empty()) {
     27             const int root = q.front();
     28             ordered[group[root]].push_back(root);
     29             for (int next : adj[q.front()]) {
     30                 if (!--count[next]) q.push(next);
     31             }
     32             q.pop();
     33             cnt++;
     34         }
     35 
     36         if (cnt != n) return {};
     37 
     38         vector<int> res;
     39         for (int i = 0; i < m; i++)
     40             if (!gcount[i]) q.push(i);
     41         while (!q.empty()) {
     42             const int root = q.front();
     43             res.insert(res.end(), ordered[root].begin(), ordered[root].end());
     44             for (int next : gadj[q.front()]) {
     45                 if (!--gcount[next]) q.push(next);
     46             }
     47             q.pop();
     48         }
     49 
     50         return res.size() == n ? res : vector<int>();
     51     }
     52 };