There are n cities labeled from 1 to n. You are given the integer n and an array connections where $connections[i] = [x_i, y_i, {cost}_i]$ indicates that the cost of connecting city $x_i$ and city $y_i$ (bidirectional connection) is ${cost}_i$.
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.
classEdge { publicint from; publicint to; publicint weight; publicEdge(int from, int to, int weight) { this.from = from; this.to = to; this.weight = weight; } }
publicintminimumCost(int n, int[][] connections) { // build graph Node[] nodes = newNode[n+1]; for (int[] conn: connections) { intn1= conn[0], n2 = conn[1], w = conn[2]; if (nodes[n1] == null) nodes[n1] = newNode(n1); if (nodes[n2] == null) nodes[n2] = newNode(n2); nodes[n1].addEdge(newEdge(n1, n2, w)); nodes[n2].addEdge(newEdge(n2, n1, w)); } intres=0, count = 1; PriorityQueue<Edge> pq = newPriorityQueue<>((a,b)->a.weight-b.weight); // Find all edges connecting to the node for (Edge e: nodes[1].edges) { pq.offer(e); } boolean[] visited = newboolean[n+1]; visited[1] = true; while (!pq.isEmpty()) { Edgeedge= pq.poll(); // Find the minimum among these edges if (visited[edge.to]) continue; // Add the chosen edge to MST if it does not form any cycle visited[edge.to] = true; res += edge.weight; count++; for (Edge e: nodes[edge.to].edges) { pq.offer(e); } } return count == n ? res : -1; } }
classSolution { publicintminimumCost(int n, int[][] connections) { int[] parents = newint[n+1], ranks = newint[n+1]; for (inti=1; i <= n; i++) { parents[i] = i; } Arrays.sort(connections, (a,b)->a[2]-b[2]); intres=0, count = 1; for (int[] conn: connections) { intp1= find(parents, conn[0]), p2 = find(parents, conn[1]); if (p1 == p2) continue; res += conn[2]; count++; union(parents, ranks, p1, p2); } return count == n ? res : -1; }
privateintfind(int[] parents, int i) { if (parents[i] == i) return i; return find(parents, parents[i]); }
privatevoidunion(int[] parents, int[] ranks, int i, int j) { if (ranks[i] < ranks[j]) { parents[i] = j; } elseif (ranks[i] > ranks[j]) { parents[j] = i; } else { ranks[i]++; parents[j] = i; } } }
1584. Min Cost to Connect All Points
You are given an array points representing integer coordinates of some points on a 2D-plane, where points[i] = [$x_i$, $y_i$].
The cost of connecting two points $[x_i, y_i]$ and $[x_j, y_j]$ is the manhattan distance between them: $|x_i - x_j| + |y_i - y_j|$, where |val| denotes the absolute value of val.
Return the minimum cost to make all points connected. All points are connected if there is exactly one simple path between any two points.
classSolution { publicintminCostConnectPoints(int[][] points) { intn= points.length, res = 0, count = 1, i = 0; boolean[] visited = newboolean[n]; visited[0] = true; PriorityQueue<int[]> pq = newPriorityQueue<>((a,b)->a[1]-b[1]); while (count++ < n) { // calculate manhattan distance for (intj=1; j < n; j++) { if (visited[j]) continue; pq.offer(newint[]{j, Math.abs(points[i][0] - points[j][0]) + Math.abs(points[i][1] - points[j][1])}); } while (visited[pq.peek()[0]]) pq.poll(); int[] p = pq.poll(); visited[p[0]] = true; res += p[1]; i = p[0]; } return res; } }
1489. Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree
Given a weighted undirected connected graph with n vertexs numbered from 0 to n - 1, and an array edges where edges[i] = [$a_i$, $b_i$, $\text{weight}_i$] represents a bidirectional and weighted edge between nodes $a_i$ and $b_i$. A minimum spanning tree (MST) is a subset of the graph's edges that connects all vertexs without cycles and with the minimum possible total edge weight.
Find all the critical and pseudo-critical edges in the given graph's minimum spanning tree (MST). An MST edge whose deletion from the graph would cause the MST weight to increase is called a critical edge. On the other hand, a pseudo-critical edge is that which can appear in some MSTs but not all.
classSolution { classEdge { publicint from; publicint to; publicint weight; publicint index; publicbooleanisSkip=false; publicEdge(int from, int to, int weight, int index) { this.from = from; this.to = to; this.weight = weight; this.index = index; } }
public List<List<Integer>> findCriticalAndPseudoCriticalEdges(int n, int[][] e) { Edge[] edges = newEdge[e.length]; for (inti=0; i < e.length; i++) { edges[i] = newEdge(e[i][0], e[i][1], e[i][2], i); } Arrays.sort(edges, (a,b)->a.weight-b.weight); int[] parents = newint[n]; for (inti=1; i < n; i++) { parents[i] = i; } List<List<Integer>> res = newArrayList<>(); res.add(newArrayList<>()); res.add(newArrayList<>()); intmin= findMstWeight(Arrays.copyOf(parents, n), newint[n], edges); for (Edge edge: edges) { edge.isSkip = true; if (min != findMstWeight(Arrays.copyOf(parents, n), newint[n], edges)) { res.get(0).add(edge.index); } edge.isSkip = false; } for (Edge edge: edges) { if (res.get(0).contains(edge.index)) continue; int[] p = Arrays.copyOf(parents, n), r = newint[n]; p[edge.from] = edge.to; r[edge.to]++; if (min == findMstWeight(p, r, edges) + edge.weight) { res.get(1).add(edge.index); } } return res; }
privateintfindMstWeight(int[] parents, int[] ranks, Edge[] edges) { intres=0; for (Edge e: edges) { if (e.isSkip) continue; intp1= find(parents, e.from), p2 = find(parents, e.to); if (p1 == p2) continue; res += e.weight; union(parents, ranks, p1, p2); } return res; }
privateintfind(int[] parents, int i) { if (parents[i] == i) return i; return find(parents, parents[i]); }
privatevoidunion(int[] parents, int[] ranks, int i, int j) { if (ranks[i] <= ranks[j]) { parents[i] = j; if (ranks[i] == ranks[j]) ranks[j]++; } else { parents[j] = i; } } }
1168. Optimize Water Distribution in a Village
There are n houses in a village. We want to supply water for all the houses by building wells and laying pipes.
For each house i, we can either build a well inside it directly with cost wells[i - 1] (note the -1 due to 0-indexing), or pipe in water from another well to it. The costs to lay pipes between houses are given by the array pipes where each pipes[j] = [$\text{house1}_j$, $\text{house2}_j$, $\text{cost}_j$] represents the cost to connect $\text{house1}_j$ and $\text{house2}_j$ together using a pipe. Connections are bidirectional, and there could be multiple valid connections between the same two houses with different costs.
Return the minimum total cost to supply water to all houses.
Example 1:
Input: n = 3, wells = [1,2,2], pipes = [[1,2,1],[2,3,1]] Output: 3 Explanation: The image shows the costs of connecting houses using pipes. The best strategy is to build a well in the first house with cost 1 and connect the other houses to it with cost 2 so the total cost is 3.
