1135. Connecting Cities With Minimum Cost

There are n cities labeled from 1 to n. You are given the integer n and an array connections where connections[i] = [xi, yi, costi] indicates that the cost of connecting city xi and city yi (bidirectional connection) is costi.

Return the minimum cost to connect all the n cities such that there is at least one path between each pair of cities. If it is impossible to connect all the n cities, return -1,

The cost is the sum of the connections’ costs used.

class Solution {
    vector<int> g;
    int find(int n) {
        return g[n] == n ? n : g[n] = find(g[n]);
    }
    void uni(int a, int b) {
        int pa = find(a), pb = find(b);
        g[pa] = g[pb] = min(pa,pb);
    }
public:
    int minimumCost(int n, vector<vector<int>>& connections) {
        g = vector<int>(n + 1);
        for(int i = 1; i <= n; i++) g[i] = i;
        int cost = 0;
        priority_queue<array<int,3>, vector<array<int,3>>, greater<array<int,3>>> pq;
        for(auto conn : connections) {
            pq.push({conn[2], conn[0], conn[1]});
        }
        while(!pq.empty()) {
            auto [c, f, t] = pq.top(); pq.pop();
            if(find(f) == find(t)) continue;
            cost += c;
            uni(f,t);
        }
        for(int i = 1; i <= n; i++) {
            if(find(g[i]) != 1) return -1;
        }
        return cost;
    }
};