List the Cables of the Cheapest Network
Solve this ProblemYou are given the possible cables between villages as a symmetric cost matrix, with all costs different. List the cables of the cheapest network that connects the villages (a minimum spanning tree, or a spanning forest when the villages cannot all be connected), each as [u, v, cost] with u < v, ordered by cost.
Kruskal's algorithm sorts the cables and keeps each one unless its two ends are already connected; union-find makes that check fast.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ n ≤ 7 villages numbered 0 … n-1; weights is a symmetric n × n matrix: weights[u][v] = 0 means no cable is possible between u and v, otherwise weights[u][v] (1 … 40) is its cost - ◆
All cable costs in the matrix are DISTINCT, so the cheapest set of cables is unique - ◆
If the villages cannot all be connected, choose the cheapest cables inside each connected part (a cheapest spanning forest) - ◆
Return the chosen cables as rows [u, v, cost] with u < v, ordered by increasing cost (an empty list if there are no cables)
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Repeatedly Take the Cheapest Cable and Test for a Loop
BruteLook at the cables from cheapest to most expensive, finding the cheapest untried one with a scan each time. Before keeping a cable (u, v), search (breadth-first) through the cables kept so far to see whether u and v are already connected: if they are, the cable would close a loop and is skipped; otherwise it is kept. Each cable costs a full scan plus a connectivity search.
O(E · (n + E))O(n²)1class Solution {
2 private boolean linked(boolean[][] chosen, int a, int b) {
3 int n = chosen.length;
4 boolean[] seen = new boolean[n];
5 Deque<Integer> queue = new ArrayDeque<>();
6 seen[a] = true;
7 queue.add(a);
8 while (!queue.isEmpty()) {
9 int u = queue.poll();
10 if (u == b) return true;
11 for (int v = 0; v < n; v++) {
12 if (chosen[u][v] && !seen[v]) {
13 seen[v] = true;
14 queue.add(v);
15 }
16 }
17 }
18 return false;
19 }
20
21 public int[][] cableList(int[][] weights) {
22 int n = weights.length;
23 List<int[]> edges = new ArrayList<>();
24 for (int u = 0; u < n; u++) {
25 for (int v = u + 1; v < n; v++) {
26 if (weights[u][v] > 0) edges.add(new int[]{u, v, weights[u][v]});
27 }
28 }
29 boolean[] tried = new boolean[edges.size()];
30 boolean[][] chosen = new boolean[n][n];
31 List<int[]> result = new ArrayList<>();
32 for (int round = 0; round < edges.size(); round++) {
33 int pick = -1;
34 for (int e = 0; e < edges.size(); e++) {
35 if (!tried[e] && (pick == -1 || edges.get(e)[2] < edges.get(pick)[2])) pick = e;
36 }
37 tried[pick] = true;
38 int[] edge = edges.get(pick);
39 if (!linked(chosen, edge[0], edge[1])) {
40 chosen[edge[0]][edge[1]] = true;
41 chosen[edge[1]][edge[0]] = true;
42 result.add(edge);
43 }
44 }
45 return result.toArray(new int[0][]);
46 }
47}Optimal — Kruskal’s Algorithm With Union-Find
OptimalSort all cables by cost once. Keep a union-find structure in which every village starts in its own group. For each cable in order, find the groups of its two ends: if they differ, the cable joins two separate parts, so keep it and merge the groups; if they are the same group, it would create a loop, so skip it. Union-find answers "are these connected?" in almost constant time, so the sorting dominates: O(E log E).
O(E log E)O(n + E)1class Solution {
2 private int find(int[] parent, int x) {
3 while (parent[x] != x) {
4 parent[x] = parent[parent[x]];
5 x = parent[x];
6 }
7 return x;
8 }
9
10 public int[][] cableList(int[][] weights) {
11 int n = weights.length;
12 List<int[]> edges = new ArrayList<>();
13 for (int u = 0; u < n; u++) {
14 for (int v = u + 1; v < n; v++) {
15 if (weights[u][v] > 0) edges.add(new int[]{u, v, weights[u][v]});
16 }
17 }
18 edges.sort((a, b) -> a[2] - b[2]);
19 int[] parent = new int[n];
20 for (int i = 0; i < n; i++) parent[i] = i;
21 List<int[]> result = new ArrayList<>();
22 for (int[] edge : edges) {
23 int a = find(parent, edge[0]), b = find(parent, edge[1]);
24 if (a != b) {
25 parent[a] = b;
26 result.add(edge);
27 }
28 }
29 return result.toArray(new int[0][]);
30 }
31}