1168

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

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

    bool unionSet(int x, int y){
        int px = find(x);
        int py = find(y);
        if(px != py){
            if(rank[px] > rank[py]){
                parent[py] = px;
            }
            else{
                parent[px] = py;
                rank[py]++;
            }
            return true;
        }
        return false;
    }
};

class Solution {
public:
    int minCostToSupplyWater(int n, vector<int>& wells, vector<vector<int>>& pipes) {
        UnionFind uf = UnionFind(n);

        for(int i=1; i<=n; i++)
            pipes.push_back({0, i, wells[i-1]});

        sort(pipes.begin(), pipes.end(), [](const vector<int> &a, const vector<int> &b){return a[2] < b[2];});

        int ans = 0;
        for(auto pipe: pipes){
            if(uf.unionSet(pipe[0], pipe[1])){
                ans += pipe[2];
            }
        }
        return ans;
    }
};