leetcode

commit a637c3e07cc050114768c31ba1710270071ec2be
parent a110587fb3bfc8a57fbdd26af6a80d9a6ded1753
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Sun, 20 Aug 2023 18:57:48 +0200

Daily Problem

Diffstat:
A
Problems/1203.cpp
 | 
53
+++++++++++++++++++++++++++++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 54 insertions(+), 0 deletions(-)
diff --git a/Problems/1203.cpp b/Problems/1203.cpp
@@ -0,0 +1,53 @@
+class Solution {
+public:
+  vector<int> sortItems(int n, int m, vector<int> &group,
+                        const vector<vector<int>> &beforeItems) {
+    for (int &g : group)
+      if (g == -1) g = m++;
+
+    vector<unordered_set<int>> gadj(m);
+    vector<vector<int>> adj(n), ordered(m);
+    vector<int> gcount(m, 0), count(n, 0);
+    queue<int> q;
+
+    for (int i = 0; i < n; i++) {
+      count[i] = beforeItems[i].size();
+      for (int elem : beforeItems[i]) {
+        adj[elem].push_back(i);
+        if (group[elem] == group[i]) continue;
+        if (gadj[group[elem]].count(group[i])) continue;
+        gadj[group[elem]].insert(group[i]);
+        gcount[group[i]]++;
+      }
+    }
+
+    int cnt = 0;
+    for (int i = 0; i < n; i++)
+      if (!count[i]) q.push(i);
+    while (!q.empty()) {
+      const int root = q.front();
+      ordered[group[root]].push_back(root);
+      for (int next : adj[q.front()]) {
+        if (!--count[next]) q.push(next);
+      }
+      q.pop();
+      cnt++;
+    }
+
+    if (cnt != n) return {};
+
+    vector<int> res;
+    for (int i = 0; i < m; i++)
+      if (!gcount[i]) q.push(i);
+    while (!q.empty()) {
+      const int root = q.front();
+      res.insert(res.end(), ordered[root].begin(), ordered[root].end());
+      for (int next : gadj[q.front()]) {
+        if (!--gcount[next]) q.push(next);
+      }
+      q.pop();
+    }
+
+    return res.size() == n ? res : vector<int>();
+  }
+};
diff --git a/README.md b/README.md
@@ -455,6 +455,7 @@ for solving problems.
 |  1162  |   Medium   | [As Far from Land as Possible](Problems/1162.cpp)                                                |
 |  1187  |    Hard    | [Make Array Strictly Increasing](Problems/1187.cpp)                                              |
 |  1202  |   Medium   | [Smallest String With Swaps](Problems/1202.cpp)                                                  |
+|  1203  |    Hard    | [Sort Items by Groups Respecting Dependencies](Problems/1203.cpp)                                |
 |  1209  |   Medium   | [Remove All Adjacent Duplicates in String II](Problems/1209.cpp)                                 |
 |  1218  |   Medium   | [Longest Arithmetic Subsequence of Given Difference](Problems/1218.cpp)                          |
 |  1232  |    Easy    | [Check If It Is a Straight Line](Problems/1232.cpp)                                              |