leetcode

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

1697.cpp (1324B)

      1 class UnionFind {
      2     int n, cnt = n;
      3     vector<int> root, size;
      4 
      5   public:
      6     UnionFind(int n) : n(n), root(n), size(n, 1) { iota(root.begin(), root.end(), 0); }
      7 
      8     int find(int x) {
      9         while (x != root[x])
     10             x = root[x] = root[root[x]];
     11         return x;
     12     }
     13 
     14     void join(int x, int y) {
     15         x = find(x), y = find(y);
     16         if (x != y) {
     17             if (size[x] > size[y]) swap(x, y);
     18             root[x] = y;
     19             size[y] += size[x];
     20             cnt--;
     21         }
     22     }
     23 
     24     int count() { return cnt; }
     25     bool connected(int x, int y) { return find(x) == find(y); }
     26 };
     27 
     28 class Solution {
     29   public:
     30     vector<bool> distanceLimitedPathsExist(int n, vector<vector<int>> &edges, vector<vector<int>> &queries) {
     31         vector<bool> res(queries.size());
     32         UnionFind uf(n);
     33 
     34         for (int i = 0; i < queries.size(); ++i)
     35             queries[i].push_back(i);
     36 
     37         const auto cmp = [](auto &a, auto &b) { return a[2] < b[2]; };
     38         sort(begin(queries), end(queries), cmp);
     39         sort(begin(edges), end(edges), cmp);
     40 
     41         int i = 0;
     42         for (auto &q : queries) {
     43             for (; i < edges.size() && edges[i][2] < q[2]; i++)
     44                 uf.join(edges[i][0], edges[i][1]);
     45             res[q[3]] = uf.connected(q[0], q[1]);
     46         }
     47         return res;
     48     }
     49 };