leetcode

Solution to some Leetcode problems written in C++

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

1203.cpp (1622B)

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