Welcome to Subscribe On Youtube
Question
Formatted question description: https://leetcode.ca/all/1135.html
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.
Example 1:
Input: n = 3, connections = [[1,2,5],[1,3,6],[2,3,1]] Output: 6 Explanation: Choosing any 2 edges will connect all cities so we choose the minimum 2.
Example 2:
Input: n = 4, connections = [[1,2,3],[3,4,4]] Output: -1 Explanation: There is no way to connect all cities even if all edges are used.
Constraints:
1 <= n <= 104
1 <= connections.length <= 104
connections[i].length == 3
1 <= xi, yi <= n
xi != yi
0 <= costi <= 105
Algorithm
Kruskal algorithm
This is a standard minimum spanning tree
problem.
There are two general solutions to the Minimum Spanning Tree (MST)
problem: Prim
and Kruskal
algorithms.
The Prim
algorithm constructs an MST from a given starting point. The general idea is as follows: let the set of vertices in graph G
be U
, arbitrarily choose a starting point a in graph G
, add it to set V
, and then find another point b
from set UV
such that the weight of any point from b
to V
is the smallest. Then, add point b
to set V
. Repeat this process until all vertices have been added to V
, constructing the MST. Since there are N
vertices, the MST has N-1
edges. Each time a point is added to set V
, it means that an MST edge is found.
On the other hand, the Kruskal
algorithm is based on the idea of greed
. First, arrange all edges from smallest to largest based on their weights
, and then select each edge in order. If the two endpoints of this edge do not belong to the same set, then merge them until all the points belong to the same set. To merge them into a set, we can use a tool like a union-find
data structure. In other words, the Kruskal algorithm is a greedy algorithm based on the union-find
data structure.
Code
-
public class Connecting_Cities_With_Minimum_Cost { class Solution { public int minimumCost(int N, int[][] connections) { Arrays.sort(connections, (a, b) -> a[2]-b[2]); int res = 0; UF uf = new UF(N); for(int [] connect : connections){ if(uf.find(connect[0]) != uf.find(connect[1])){ uf.union(connect[0], connect[1]); res += connect[2]; } if(uf.count == 1){ return res; } } return -1; } } class UF{ int [] parent; int [] size; int count; public UF(int n){ parent = new int[n+1]; size = new int[n+1]; for(int i = 0; i<=n; i++){ parent[i] = i; size[i] = 1; } this.count = n; } public int find(int i){ if(i != parent[i]){ parent[i] = find(parent[i]); } return parent[i]; } public void union(int p, int q){ int i = find(p); int j = find(q); if(size[i] > size[j]){ parent[j] = i; size[i] += size[j]; }else{ parent[i] = j; size[j] += size[i]; } this.count--; } } }
-
// OJ: https://leetcode.com/problems/connecting-cities-with-minimum-cost/ // Time: O(ElogE) // Space: O(N) class UnionFind { vector<int> id; int cnt; public: UnionFind(int n) : id(n), cnt(n) { iota(begin(id), end(id), 0); } int find(int a) { return id[a] == a ? a : (id[a] = find(id[a])); } void connect(int a, int b) { int p = find(a), q = find(b); if (p == q) return; --cnt; id[p] = q; } bool connected(int a, int b) { return find(a) == find(b); } int getCount() { return cnt; } }; class Solution { public: int minimumCost(int n, vector<vector<int>>& E) { sort(begin(E), end(E), [](auto &a, auto &b) { return a[2] < b[2]; }); UnionFind uf(n); int ans = 0; for (auto &e : E) { int u = e[0] - 1, v = e[1] - 1; if (uf.connected(u, v)) continue; uf.connect(u, v); ans += e[2]; } return uf.getCount() == 1 ? ans : -1; } };
-
class Solution: def minimumCost(self, n: int, connections: List[List[int]]) -> int: def find(x): if p[x] != x: p[x] = find(p[x]) return p[x] connections.sort(key=lambda x: x[2]) p = list(range(n)) # parent[], uf ans = 0 for x, y, cost in connections: x, y = x - 1, y - 1 if find(x) == find(y): continue p[find(x)] = find(y) ans += cost n -= 1 if n == 1: return ans return -1
-
func minimumCost(n int, connections [][]int) (ans int) { p := make([]int, n) for i := range p { p[i] = i } sort.Slice(connections, func(i, j int) bool { return connections[i][2] < connections[j][2] }) var find func(int) int find = func(x int) int { if p[x] != x { p[x] = find(p[x]) } return p[x] } for _, e := range connections { x, y, cost := e[0]-1, e[1]-1, e[2] if find(x) == find(y) { continue } p[find(x)] = find(y) ans += cost n-- if n == 1 { return } } return -1 }
-
function minimumCost(n: number, connections: number[][]): number { const p = new Array(n); for (let i = 0; i < n; ++i) { p[i] = i; } const find = (x: number): number => { if (p[x] !== x) { p[x] = find(p[x]); } return p[x]; }; connections.sort((a, b) => a[2] - b[2]); let ans = 0; for (const [x, y, cost] of connections) { if (find(x - 1) == find(y - 1)) { continue; } p[find(x - 1)] = find(y - 1); ans += cost; if (--n == 1) { return ans; } } return -1; }