leetcode

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 };