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]; } };
No comments:
Post a Comment