1584

class Solution {
public:
    struct node{
        int pt1, pt2, dist;

        bool operator()(node& a, node& b){
            return a.dist > b.dist;
        }
    };

    class UnionFind{
        vector<int> parent, rank;

        public:
        int edges=0;
        UnionFind(int n){
            parent.resize(n);
            rank.resize(n, 0);
            for(int i=0; i<n; i++)
                parent[i]=i;
        }

        int findParent(int x){
            return (x == parent[x]) ? x : (parent[x] = findParent(parent[x]));
        }

        bool Union(int x, int y){
            int px = findParent(x);
            int py = findParent(y);

            if(px == py) return false;

            if(rank[px] > rank[py]){
                parent[py] = px;
            }
            else{
                parent[px] = py;
                rank[py]++;
            }
            edges++;
            return true;
        }
    };

    int minCostConnectPoints(vector<vector<int>>& points) {
        priority_queue<node, vector<node>, node> pq;
        int n=points.size();

        for(int i=0; i<n; i++){
            for(int j=i+1; j<n; j++){
                int dist = abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1]);
                pq.push({i, j, dist});
            }
        }

        int result=0;
        UnionFind uf(n);

        while(!pq.empty()){
            node curr = pq.top();
            pq.pop();

            if(uf.Union(curr.pt1, curr.pt2))
                result += curr.dist;

            if(uf.edges == n-1) return result;
        }
        return 0;
    }
};