Leetcode 1135. Connecting Cities With Minimum Cost

https://leetcode.com/problems/connecting-cities-with-minimum-cost/description/

Description:

There are N cities numbered from 1 to N.
You are given connections, where each connections[i] = [city1, city2, cost] represents the cost to connect city1 and city2 together. (A connection is bidirectional: connecting city1 and city2 is the same as connecting city2 and city1.)
Return the minimum cost so that for every pair of cities, there exists a path of connections (possibly of length 1) that connects those two cities together. The cost is the sum of the connection costs used. If the task is impossible, return -1.

Notes:

This question asks for the weights of the minimum spanning tree. There are very good resource online to this topic. For example,

https://www.geeksforgeeks.org/kruskals-minimum-spanning-tree-algorithm-greedy-algo-2/

The key algorithm involved is the so called union-find algorithm, which can be find in the below link,

https://www.geeksforgeeks.org/union-find/

See the code below:

class Solution {
public:
    int minimumCost(int N, vector<vector<int>>& conections) {
        sort(conections.begin(), conections.end(), [](auto &a, auto &b){return a[2] < b[2];});
        vector<int> ps(N+1, 0);
        for(int i=1; i<=N; ++i) ps[i] = i;
        int res = 0, ct = 1;
        for(auto &a : conections) {
            int x = find(a[0], ps), y = find(a[1], ps);
            if(x != y) {
            ps[x] = y;
            res += a[2];
            ++ct;
            if(ct==N) return res;
            }
        }
        return -1;
    }
private:
    int find(int x, vector<int> &ps) {
        if(ps[x] != x) ps[x] = find(ps[x], ps);
        return ps[x];
    }
};