leetcode

commit a4868eb2e020dacfffda0b45b4605ed2c425dcea
parent 0c45af7adbc5c6cabca3ed186b0a6640b75d1c46
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Sun, 15 Jan 2023 15:51:54 +0100

Daily Problem

Diffstat:
A
Problems/2421.cpp
 | 
54
++++++++++++++++++++++++++++++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 55 insertions(+), 0 deletions(-)
diff --git a/Problems/2421.cpp b/Problems/2421.cpp
@@ -0,0 +1,54 @@
+class UnionFind {
+  int n, cnt = n;
+  vector<int> root, size;
+
+public:
+  UnionFind(int n) : n(n), root(n), size(n, 1) {
+    iota(root.begin(), root.end(), 0);
+  }
+
+  int find(int x) {
+    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--;
+    }
+  }
+};
+
+class Solution {
+public:
+  int numberOfGoodPaths(vector<int> &vals, vector<vector<int>> &edges) {
+    int n = vals.size();
+    map<int, vector<int>> valuesToNodes;
+    vector<vector<int>> adj(n);
+    UnionFind uf(n);
+
+    for (auto &edge : edges) {
+      adj[edge[0]].push_back(edge[1]);
+      adj[edge[1]].push_back(edge[0]);
+    }
+
+    for (int i = 0; i < n; i++) valuesToNodes[vals[i]].push_back(i);
+
+    int goodPaths = 0;
+    for (auto &[value, nodes] : valuesToNodes) {
+      for (int node : nodes) {
+        for (int neighbor : adj[node]) {
+          if (vals[node] >= vals[neighbor]) { uf.join(node, neighbor); }
+        }
+      }
+      unordered_map<int, int> group;
+      for (int u : nodes) group[uf.find(u)]++;
+      for (auto &[_, size] : group) goodPaths += (size * (size + 1) / 2);
+    }
+    return goodPaths;
+  }
+};
diff --git a/README.md b/README.md
@@ -309,6 +309,7 @@ for solving problems.
 |  2368  |   Medium   | [Reachable Nodes With Restrictions](Problems/2368.cpp)                                           |
 |  2374  |   Medium   | [Node With Highest Edge Score](Problems/2374.cpp)                                                |
 |  2390  |   Medium   | [Removing Stars From a String](Problems/2390.cpp)                                                |
+|  2421  |   Medium   | [Number of Good Paths](Problems/2421.cpp)                                                        |
 |  2461  |   Medium   | [Maximum Sum of Distinct Subarrays With Length K](Problems/2461.cpp)                             |
 |  2465  |    Easy    | [Number of Distinct Averages](Problems/2465.cpp)                                                 |
 |  2466  |   Medium   | [Count Ways To Build Good Strings](Problems/2466.cpp)                                            |