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.
其实union-find也没有那么难。一个union函数,一个find函数,哦了。
https://leetcode.com/problems/connecting-cities-with-minimum-cost/discuss/344867/Java-Kruskal's-Minimum-Spanning-Tree-Algorithm-with-Union-Find
class Solution { int[] parent; int n; private void union(int x, int y) { int px = find(x); int py = find(y); if (px != py) { parent[px] = py; n--; } } private int find(int x) { if (parent[x] == x) { return parent[x]; } parent[x] = find(parent[x]); // path compression return parent[x]; } public int minimumCost(int N, int[][] connections) { parent = new int[N + 1]; n = N; for (int i = 0; i <= N; i++) { parent[i] = i; } Arrays.sort(connections, (a, b) -> (a[2] - b[2])); int res = 0; for (int[] c : connections) { int x = c[0], y = c[1]; if (find(x) != find(y)) { res += c[2]; union(x, y); } } return n == 1 ? res : -1; } }