← DSA Atlas
Dedicated problem page · #1135

Connecting Cities With Minimum Cost

MediumShortest Path, Dijkstra and Minimum Spanning TreeMinimum spanning tree (Kruskal)Union-Find + edge sorting
Solve on LeetCode ↗
1135
MediumShortest Path, Dijkstra and Minimum Spanning TreeUnion-Find + edge sortingMinimum spanning tree (Kruskal)

Connecting Cities With Minimum Cost

There are n cities labeled 1..n. You are given connections where each entry [city1, city2, cost] is a bidirectional link that can be built for the given cost. Return the minimum total cost to connect all cities so that every pair is reachable, or -1 if it is impossible to connect them all.

Open official problem prompt ↗
In plain English

Find the cheapest set of links that makes all n cities mutually reachable.

Picture it like this

A road department with a fixed map of possible roads and their prices wants every town linked; it builds the cheapest roads first, skipping any that would connect two towns already joined by another route.

Example
Input
n = 3, connections = [[1,2,5],[1,3,6],[2,3,1]]
Output
6
Why
Choosing edges 2-3 (cost 1) and 1-2 (cost 5) connects all three cities for 6, the cheapest spanning tree.
Constraints
1 <= n <= 10^41 <= connections.length <= 10^4connections[i].length == 31 <= city1, city2 <= ncity1 != city20 <= cost <= 10^5
Pattern lesson

See the pattern, then code

Minimum spanning tree (Kruskal)
Recognition clue

You must connect every node using a subset of weighted edges at minimum total weight, with no requirement on path structure - that is the textbook minimum spanning tree signal.

↗
Shortest Path, Dijkstra and Minimum Spanning Tree

Shortest paths with non-negative weights or minimum-cost graph connection.. Greedily add the cheapest edge that joins two currently separate components; if it would form a cycle skip it. A spanning tree of n nodes needs exactly n-1 accepted edges.

New words, made simpleKnow these before the algorithm
Spanning tree
A cycle-free subset of edges that touches every vertex; for n vertices it has exactly n-1 edges.
Union-Find (DSU)
A structure that tracks which component each node is in and merges components in near-constant time.
Cut / cycle
Adding an edge inside one existing component creates a cycle and is wasteful for an MST.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Try all edge subsets

Exponential; impossible for 10^4 edges.

Enumerate subsets of edges and keep the cheapest that spans the graph.

Time O(2^E)Space O(E)
Best choiceKruskal with Union-Find

Simple, provably optimal via the cut property, and fast enough for the limits.

Sort edges by cost and union endpoints greedily, skipping edges that would create a cycle.

Time O(E log E)Space O(n)
The rule we keep true

Invariant

The set of accepted edges is always a forest (acyclic), and at every step it is a subset of some minimum spanning tree.

Why this is correct

Reasoning

By the cut property, the lightest edge crossing between two components is safe to include in some MST. Processing edges cheapest-first and adding any that joins distinct components repeatedly applies this safe choice, so the final forest is a minimum spanning tree if one exists.

The algorithm in three movesSay these aloud before coding
1Sort all connections by ascending cost

sorted edges: (2,3,1),(1,2,5),(1,3,6)

2Initialize Union-Find over the n cities

take 2-3: total=1, comps={1},{2,3}

3Scan edges cheapest-first, uniting endpoints that are in different components and adding that cost

take 1-2: total=6, comps={1,2,3}, used=2=n-1

4Count accepted edges; if fewer than n-1 the graph is disconnected, return -1

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
2-3:10
1-2:51
1-3:62
1 · Read[[1,2,5],[1,3,6],[2,3,1]]
2 · AskWhich order minimizes greedy choices?
3 · Update state(2,3,1),(1,2,5),(1,3,6)
4 · ResultCheapest first.
Key takeaway

Edges sorted by cost; Kruskal accepts 2-3 then 1-2 to span all cities.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 3-8Union-Find with path halving

    find returns each node's component root while flattening the tree for speed.

  2. 2
    Lines 9-9Sort edges

    Ordering by cost lets the greedy scan always consider the cheapest available link.

  3. 3
    Lines 12-18Greedy union

    Only edges joining two different roots are accepted, adding their cost and counting toward the n-1 needed.

  4. 4
    Lines 19-19Connectivity check

    If fewer than n-1 edges were accepted the graph cannot be spanned, so return -1.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • n == 1 needs 0 edges and costs 0
  • The graph is disconnected, so no spanning tree exists and the answer is -1
  • Duplicate edges between the same pair with different costs - the cheaper one is used naturally
!

Common beginner mistakes

  • Cities are labeled from 1, so size the parent array as n+1 or remap to 0-based
  • Forgetting the used == n-1 check and returning a partial-tree cost for a disconnected graph
  • Adding an edge without checking roots, which creates cycles and overcounts cost
Check your understanding

Why can we stop as soon as we have accepted n-1 edges?

More in Shortest Path, Dijkstra and Minimum Spanning Tree

#743Network Delay TimeSingle-source shortest path#332Reconstruct ItineraryEulerian path (Hierholzer's algorithm)#505The Maze IIWeighted shortest path on a grid#778Swim in Rising WaterMinimize the maximum along a path (minimax path)#787Cheapest Flights Within K StopsShortest path with a hop limit#815Bus RoutesUnweighted shortest path (fewest transfers)