LeetCode 每日一题

 1 class Solution {
 2 public:
 3     struct node{
 4         int p1, p2, d;
 5     }line[1000005];
 6     static bool cmp(node x, node y) {
 7         return x.d < y.d;
 8     }
 9     int fa[1000005];
10     int fi(int x) {
11         return fa[x] == x ? x : fa[x] = fi(fa[x]);
12     }
13     int minCostConnectPoints(vector<vector<int>>& points) {
14         int n = points.size(), m = 0, ans = 0;
15         for (int i = 0; i < n; i++) fa[i] = i;
16         for (int i = 0; i < n; i++) {
17             for (int j = i + 1; j < n; j++) {
18                 line[m].p1 = i; line[m].p2 = j; 
19                 line[m].d = abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1]);
20                 m++;
21             }
22         }
23         sort(line, line + m, cmp);
24         for (int i = 0; i < m; i++) {
25             int fx = fi(line[i].p1);
26             int fy = fi(line[i].p2);
27             if (fx != fy) {
28                 fa[fx] = fy;
29                 ans += line[i].d;
30             }
31         }
32         return ans;
33     }
34 };