leetcode

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

2492.cpp (853B)

      1 class UnionFind {
      2     int n;
      3     vector<int> root, rank, res;
      4 
      5   public:
      6     UnionFind(int n) : n(n), root(n), rank(n, 1), res(n, INT_MAX) { 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, int val) {
     15         x = find(x), y = find(y);
     16         if (x != y) {
     17             if (rank[x] > rank[y]) swap(x, y);
     18             res[y] = min(res[x], res[y]);
     19             root[x] = y;
     20             rank[y] += rank[x];
     21         }
     22         res[y] = min(val, res[y]);
     23     }
     24 
     25     int mini(int x) { return res[find(x)]; }
     26 };
     27 
     28 class Solution {
     29   public:
     30     int minScore(int n, vector<vector<int>> &roads) {
     31         UnionFind uf(n + 1);
     32         for (auto &r : roads)
     33             uf.join(r[0], r[1], r[2]);
     34         return uf.mini(n);
     35     }
     36 };