Hints — p66 Min Cost to Connect All Points

Hint 1. “Connect all points with minimum total cost” = Minimum Spanning Tree (MST) on the complete graph whose edge weights are pairwise Manhattan distances.

Hint 2. Two classical MST algorithms:

• Kruskal: sort all edges, scan in order, add if endpoints are in different components (Union-Find).
• Prim: grow MST from a starting node; at each step add the cheapest edge leaving the current tree.

Both correct via the cut property (cheapest edge crossing any cut belongs to some MST).

Hint 3. Edge count = V·(V-1)/2 ≈ V². That’s DENSE. Array-based Prim is O(V²); heap-Prim and Kruskal are O(V² log V). Array-Prim wins.

Hint 4. Array-Prim implementation: keep min_cost[v] = cheapest edge from {in-MST} to v. Each iteration: pick the unfinished node u with smallest min_cost[u]; add its cost to total; update min_cost[v] for all unfinished v using dist(u, v).

Hint 5. Initialize min_cost[0] = 0 (so the first iteration picks node 0 with cost 0). After V iterations all nodes are in the MST and total is the answer.

If stuck: see solution.py.