leetcode

0 class UnionFind {

1 int n;

2 vector<int> root, rank;

3

4 public:

5 UnionFind(int n) : n(n), root(n), rank(n, 1) { 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) {

14 x = find(x), y = find(y);

15 if (x != y) {

16 if (rank[x] > rank[y]) swap(x, y);

17 root[x] = y;

18 rank[y] += 1;

19 n--;

20 }

21 }

22

23 int count() { return n; }

24 bool connected(int x, int y) { return find(x) == find(y); }

25 };

26

27 class Solution {

28 typedef array<int, 3> edge;

29 typedef vector<int> point;

30

31 int distance(const point &p1, const point &p2) { return abs(p1[0] - p2[0]) + abs(p1[1] - p2[1]); }

32

33 public:

34 int minCostConnectPoints(vector<vector<int>> &points) {

35 auto cmp = [](const edge &a, const edge &b) { return a[2] > b[2]; };

36 priority_queue<edge, vector<edge>, decltype(cmp)> pq(cmp);

37 UnionFind uf(points.size());

38

39 for (int i = 0; i < points.size(); i++)

40 for (int j = i + 1; j < points.size(); j++)

41 pq.push({i, j, distance(points[i], points[j])});

42

43 int res = 0;

44 while (uf.count() != 1) {

45 auto [s, d, w] = pq.top();

46 pq.pop();

47 if (uf.connected(s, d)) continue;

48 uf.join(s, d);

49 res += w;

50 }

51 return res;

52 }

53 };