leetcode

commit a8f78860b12f49e6df4c3532107f8c62828a6a48
parent 35f23abc81676fb7e3d07462f932211ebf74bd85
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Sat, 24 Feb 2024 13:07:18 +0000

1 Daily Problem

Diffstat:
A
Problems/2092.cpp
 | 
66
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 67 insertions(+), 0 deletions(-)
diff --git a/Problems/2092.cpp b/Problems/2092.cpp
@@ -0,0 +1,66 @@
+int n, cnt = n;
+mutable vector<int> root;
+vector<int> size;
+
+public:
+UnionFind(int n) : n(n), root(n), size(n, 1) { iota(root.begin(), root.end(), 0); }
+UnionFind(const UnionFind &uf) : n(uf.n), cnt(uf.cnt), root(uf.root), size(uf.size) {}
+
+int find(int x) const {
+    while (x != root[x])
+        x = root[x] = root[root[x]];
+    return x;
+}
+
+void join(int x, int y) {
+    x = find(x), y = find(y);
+    if (x != y) {
+        if (size[x] > size[y]) swap(x, y);
+        root[x] = y;
+        size[y] += size[x];
+        cnt--;
+    }
+}
+
+void reset(int x) {
+    root[x] = x;
+    size[x] = 0;
+}
+
+int count() const { return cnt; }
+bool connected(int x, int y) const { return find(x) == find(y); }
+}
+;
+
+class Solution {
+  public:
+    vector<int> findAllPeople(int n, vector<vector<int>> &meetings, int firstPerson) {
+        sort(begin(meetings), end(meetings), [](const auto &m1, const auto &m2) { return m1[2] < m2[2]; });
+
+        int first = 0;
+        UnionFind uf(n);
+        uf.join(0, firstPerson);
+
+        meetings.push_back({0, 0, INT_MAX});
+        uf.join(meetings[0][0], meetings[0][1]);
+        for (int i = 1; i < size(meetings); i++) {
+            if (meetings[i][2] == meetings[i - 1][2]) {
+                uf.join(meetings[i][0], meetings[i][1]);
+            } else {
+                for (int j = first; j < i; j++) {
+                    if (uf.connected(meetings[j][0], 0)) continue;
+                    uf.reset(meetings[j][0]);
+                    uf.reset(meetings[j][1]);
+                }
+                first = i;
+                uf.join(meetings[i][0], meetings[i][1]);
+            }
+        }
+
+        vector<int> res;
+        for (int i = 0; i < n; i++) {
+            if (uf.connected(i, 0)) res.push_back(i);
+        }
+        return res;
+    }
+};
diff --git a/README.md b/README.md
@@ -970,6 +970,7 @@ for solving problems.
 |  2085  |    Easy    | [Count Common Words With One Occurrence](Problems/2085.cpp)                                        |
 |  2090  |   Medium   | [K Radius Subarray Averages](Problems/2090.cpp)                                                    |
 |  2091  |   Medium   | [Removing Minimum and Maximum From Array](Problems/2091.cpp)                                       |
+|  2092  |    Hard    | [Find All People With Secret](Problems/2092.cpp)                                                   |
 |  2095  |   Medium   | [Delete the Middle Node of a Linked List](Problems/2095.cpp)                                       |
 |  2101  |   Medium   | [Detonate the Maximum Bombs](Problems/2101.cpp)                                                    |
 |  2104  |   Medium   | [Sum of Subarray Ranges](Problems/2104.cpp)                                                        |