1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
| class Solution {
private:
vector<int> f, rank;
struct Edge {
int v, u, w;
bool operator < (const Edge& e) const {
return w < e.w;
}
};
int find(int x) {
return f[x] == x ? x : f[x] = find(f[x]);
}
bool _union(int x, int y) {
int fx = find(x), fy = find(y);
if (fx == fy) return false;
else if (rank[fx] > rank[fy])
swap(fx, fy);
rank[fy] += rank[fx];
f[fx] = fy;
return true;
}
public:
int minCostConnectPoints(vector<vector<int>>& points) {
int n = points.size();
if (n <= 1) return 0;
vector<Edge> graph;
for (int i = 0; i < n; ++i)
for (int j = i + 1; j < n; ++j)
graph.push_back({i, j,
abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1])});
f = vector<int>(n, 0);
rank = vector<int>(n, 1);
for (int i = 0; i < n; ++i)
f[i] = i;
sort(graph.begin(), graph.end());
int ans = 0;
for (Edge& e : graph)
if (_union(e.v, e.u)) {
ans += e.w;
if (--n == 1)
return ans;
}
return -1;
}
};
|