Dense Power Grid

EasyAdvanced Graphs

Problem

A utility must connect n villages to one power grid. A survey priced a line between every pair of villages: cost[i][j] is the price of a line between i and j (the matrix is symmetric and cost[i][i] = 0).

Return the minimum total price of lines so that all villages are connected.

Example 1

Input:
cost = [[0,4,1,3],[4,0,2,5],[1,2,0,6],[3,5,6,0]]
Output:
6

Lines 0–2 (1), 2–1 (2) and 0–3 (3).

Example 2

Input:
cost = [[0]]
Output:
0

Example 3

Input:
cost = [[0,7],[7,0]]
Output:
7

Constraints

  • 1 ≤ n ≤ 300
  • 1 ≤ cost[i][j] ≤ 10^5 for i ≠ j
  • cost[i][j] = cost[j][i]

Hint

Show the first hint

Every pair has a price, so there are about n²/2 edges. A spanning tree uses only n - 1 of them.

Walkthrough

How to approach it

01Clarify before coding

  • Is every pair priced? Yes, the graph is complete.
  • Is the matrix symmetric? Yes.
  • One village? Cost 0.

02Brute force

List all n(n-1)/2 pairs, sort them and run Kruskal.

Cost: O(n² log n) time and O(n²) extra memory: works for n = 300 but wastes effort on a dense graph.

The rest of the walkthrough is in the app

The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.

Solve it in the browserStart free

This problem is part of Pro.