1584.cpp (1447B)
1 class UnionFind { 2 int n; 3 vector<int> root, rank; 4 5 public: 6 UnionFind(int n) : n(n), root(n), rank(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 (rank[x] > rank[y]) swap(x, y); 18 root[x] = y; 19 rank[y] += 1; 20 n--; 21 } 22 } 23 24 int count() { return n; } 25 bool connected(int x, int y) { return find(x) == find(y); } 26 }; 27 28 class Solution { 29 typedef array<int, 3> edge; 30 typedef vector<int> point; 31 32 int distance(const point &p1, const point &p2) { return abs(p1[0] - p2[0]) + abs(p1[1] - p2[1]); } 33 34 public: 35 int minCostConnectPoints(vector<vector<int>> &points) { 36 auto cmp = [](const edge &a, const edge &b) { return a[2] > b[2]; }; 37 priority_queue<edge, vector<edge>, decltype(cmp)> pq(cmp); 38 UnionFind uf(points.size()); 39 40 for (int i = 0; i < points.size(); i++) 41 for (int j = i + 1; j < points.size(); j++) 42 pq.push({i, j, distance(points[i], points[j])}); 43 44 int res = 0; 45 while (uf.count() != 1) { 46 auto [s, d, w] = pq.top(); 47 pq.pop(); 48 if (uf.connected(s, d)) continue; 49 uf.join(s, d); 50 res += w; 51 } 52 return res; 53 } 54 };