leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

2492.cpp (853B)

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