Connecting Cities With Minimum Cost

Intuition

Connecting every city with the least total cost is a Minimum Spanning Tree problem on the given weighted edges. Kruskal's algorithm processes edges from cheapest to most expensive and keeps an edge only if it links two cities that are not yet connected. A union-find structure tracks which cities already share a component, so we can reject an edge whose endpoints are already merged. A spanning tree over n cities needs exactly n-1 accepted edges; if fewer merges succeed, the graph is split into multiple pieces and connecting everything is impossible, so we return -1.

Algorithm walkthrough

1. 1Create a union-find over cities 1..n, each city its own root.
2. 2Sort all connections in non-decreasing order of cost.
3. 3For each connection, look up the roots of both cities.
4. 4If the roots differ, union them, add the cost to the total, and increment a counter of successful merges.
5. 5After processing every edge, check whether exactly n-1 merges happened.
6. 6Return the accumulated total if the graph is fully connected, otherwise return -1.

Implementation

class Solution:
    def minimumCost(self, n: int, connections: List[List[int]]) -> int:
        parent = list(range(n + 1))

        def find(x: int) -> int:
            while parent[x] != x:
                parent[x] = parent[parent[x]]
                x = parent[x]
            return x

        connections.sort(key=lambda c: c[2])
        total = 0
        used = 0
        for a, b, cost in connections:
            ra, rb = find(a), find(b)
            if ra != rb:
                parent[ra] = rb
                total += cost
                used += 1
        return total if used == n - 1 else -1