Builds on Union-Find, which you haven’t finished yet.
Minimum Spanning Tree (Kruskal's, built on Union-Find)
There are n cities, labeled 1 to n. Each connections[i] = [xi, yi, cost_i] says you can build a two-way link between city xi and city yi for cost_i.
Choose links so that every city can reach every other city through built links, and pay as little as possible in total. Return that smallest total, or -1 if even building every link leaves some cities cut off.
2-3 for 1 and 1-2 for 5.Kruskal's MST
edge list sorted by weight ➔ union by rank/size ➔ connect components- You need the cheapest route from one source to the other nodes, as in Network Delay Time (LC 743), not the cheapest set of edges that joins everything. See Dijkstra
| 1 | from typing import List |
| 2 | |
| 3 | def kruskal_mst(n: int, edges: List[List[int]]) -> int: |
| 4 | """Kruskal's MST (Connecting Cities With Minimum Cost): cheapest total cost to join |
| 5 | nodes 1..n, or -1. |
| 6 | Time: O(E log E) | Space: O(V) |
| 7 | """ |
| 8 | parent = list(range(n + 1)) |
| 9 | |
| 10 | def find(x: int) -> int: |
| 11 | while parent[x] != x: |
| 12 | parent[x] = parent[parent[x]] # Path halving: skip a level on every step |
| 13 | x = parent[x] |
| 14 | return x |
| 15 | |
| 16 | edges.sort(key=lambda e: e[2]) # Cheapest edges first |
| 17 | mst_cost = 0 |
| 18 | edges_count = 0 |
| 19 | |
| 20 | for u, v, w in edges: |
| 21 | root_u, root_v = find(u), find(v) |
| 22 | if root_u != root_v: # Different groups: this edge is safe to take |
| 23 | parent[root_u] = root_v # Join the roots, not the nodes |
| 24 | mst_cost += w |
| 25 | edges_count += 1 |
| 26 | if edges_count == n - 1: |
| 27 | break # A spanning tree has exactly n - 1 edges |
| 28 | |
| 29 | return mst_cost if edges_count == n - 1 else -1 # Fewer edges: not connected |
find gives one root to exactly the nodes they connect.Sort edges by weight and take each edge whose ends have different roots, find(u) != find(v), joining the two groups. The cheapest edge between two separate groups is always safe to take: any full wiring must cross that gap somewhere, and swapping in the cheaper edge never costs more; an edge whose ends already share a root would only close a cycle, so skipping it loses nothing. The trap is the final check: fewer than n - 1 edges taken means the graph is not connected, so return -1 instead of the partial cost.
See it run
Kruskal's minimum spanning tree, step by step
parent [1, 2, 3, 4]mst_cost 0edges_count 0
Each line is a road with its cost beside it. A node shows its number, a slash, then its root. The row under the graph is edges sorted by weight, written as u-v:cost.
testthe edge being checked, and its two end nodestakean edge added to the treeskipan edge whose ends already share a root
edges.sort puts the cheapest edge first. Every node is its own root, so the groups are 4 single nodes.
Gotcha 1 of 4
- The trap
Gotcha 1: Returning
mst_costwithout checkingedges_countMistakereturn mst_costFixreturn mst_cost if edges_count == n - 1 else -1What happens: A tree that joins
nnodes has exactlyn - 1edges. If the edges run out with fewer, some cities are still in separate groups.mst_costis then the cost of a partial wiring. The problem asks for-1in that case.Example: Connecting Cities With Minimum Cost (LC 1135): n = 4, connections = [[1, 2, 3], [3, 4, 4]]Mistake: returns 7Fix: returns -1
Deep Dive
Why the cheapest edge between two groups is safe
A spanning tree joins all n nodes with n - 1 edges and no cycle. We want the one with the lowest total cost.
At any moment find splits the nodes into groups. Take the cheapest edge e that joins two different groups. Look at any full wiring that does not use e. That wiring must connect the two groups somewhere, so it has some edge f that crosses between them. Now remove f and add e. The wiring is still connected, and its cost did not go up, because e is no more expensive than f.
So some cheapest wiring uses e. Taking e never rules out a cheapest wiring, and the same argument holds after every join.
An edge whose two ends share a root is different. Both ends are already connected, so the edge only closes a cycle. Skipping it loses nothing.
One trace: an edge taken and an edge skipped
The board runs kruskal_mst on n = 4 and connections = [[1, 2, 6], [2, 3, 1], [2, 4, 3], [3, 4, 4]]. After the sort the order is 2-3:1, 2-4:3, 3-4:4 and 1-2:6.
Edge 2-3 has roots 2 and 3, which differ, so it is taken and parent[2] = 3. Edge 2-4 has roots 3 and 4, so it is taken and parent[3] = 4. Now nodes 2, 3 and 4 share root 4.
Edge 3-4 has root 4 on both ends. Taking it would close the triangle 2-3-4, so it is skipped. This is the step marked as skipped on the board.
Edge 1-2 has roots 1 and 4, so it is taken, and edges_count reaches n - 1 = 3. The cost is 1 + 3 + 6 = 10. The loop stops at once.
The trap: a graph that is not connected
The loop ends when edges_count is n - 1, or when the edges run out. If the edges run out first, some nodes are in separate groups, and no wiring can join them all.
Example: Connecting Cities With Minimum Cost (LC 1135) with n = 4 and connections = [[1, 2, 3], [3, 4, 4]]. Both edges are taken, so mst_cost is 7 and edges_count is 2. But n - 1 is 3. The cities 1 and 2 never join the cities 3 and 4. The right answer is -1, and return mst_cost would return 7.
The other trap is the join itself. parent[root_u] = root_v links the roots. Writing parent[u] = root_v moves only u, so a group can look split. For the graph in the trace, that mistake returns 8 and not 10.
The cost, and how it differs from Dijkstra
The sort costs O(E log E). Each find with path halving is close to constant. So the total is O(E log E) time, and parent takes O(V) space.
Min Cost to Connect All Points (LC 1584) has no edge list. Every pair of points is an edge, so 1000 points give 499500 edges. Build them all, and then run the same loop.
Dijkstra (the cheapest-first card) and this card both pick cheap edges, but they answer different questions. Dijkstra finds the cheapest route from one source to each node. Kruskal finds the cheapest set of edges that joins all nodes.
Example: take edges 1-2:2, 2-3:2 and 1-3:3. The cheapest wiring uses 1-2 and 2-3, and costs 4. The cheapest routes from node 1 use 1-2 and 1-3, because node 3 is cheapest to reach directly. Those two edges cost 5.
60-Second Pitch
"I need the cheapest set of edges that joins every node, so I use Kruskal's algorithm with Union-Find. I sort the edges by weight. For each edge, I check whether its two ends already have the same root. If the roots differ, this is the cheapest edge between two groups, so I link the roots and add its weight. If the roots are equal, the edge would close a cycle, so I skip it. This is safe because any full wiring must cross between two groups somewhere, and swapping in the cheaper edge never raises the cost. I stop at n - 1 edges. If I run out of edges before that, the graph is not connected and I return -1. The time is O(E log E) for the sort."
Common Questions
- Why does taking the cheapest edge between two groups never hurt?
Any full wiring must cross between those two groups with some edge. Replace that edge with the cheapest one. The wiring stays connected and costs no more. So a cheapest wiring that uses the edge always exists.
- What are the time and space complexity?
O(E log E) time for the sort. The loop makes E calls to
find, each close to constant with path halving. The space is O(V) forparent. For Min Cost to Connect All Points (LC 1584), E is about V squared divided by 2.- How do you know the graph is not connected?
A spanning tree has exactly
n - 1edges. If the loop ends withedges_countbelown - 1, some nodes are in separate groups. Return -1.- Kruskal or Prim: which would you pick?
Kruskal is short when the input is an edge list, because it needs only a sort and Union-Find. Prim grows one tree with a heap, and it suits a dense graph given as a matrix. Both find a minimum spanning tree.
- Is the minimum spanning tree unique?
Not always. If two edges have the same weight, two different trees can have the same lowest cost. The total cost is always the same. Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree (LC 1489) asks which edges are in every tree.
SWE Reasoning
Spot it
- The task is to connect all points, cities, computers or pipes at the lowest total cost.
- The answer is one total cost, not a path between two nodes.
- The input is a list of weighted edges, or every pair of points can be an edge.
- The wiring needs no cycle, because a cycle only repeats a link that already exists.
- The statement says to return -1 or false when the nodes cannot all be joined.
The invariant, step by step
parentstarts with every node as its own root, so every node is its own group.mst_costandedges_countare 0.edges.sortputs the cheapest edge first.- For each edge, compute
find(u)andfind(v). - If the roots differ, this is the cheapest edge left between two groups. Link the roots, add
wtomst_costand add 1 toedges_count. - If the roots are equal, the ends are already connected. Skip the edge.
- Stop when
edges_count == n - 1. If the edges run out first, return -1.
Traps
- No final check. Returning
mst_costwhenedges_countis belown - 1gives the cost of a partial wiring. Return -1. - Sorting by the wrong field. The weight is
e[2]. Sorting by a city number breaks the cheapest-edge rule. - Linking nodes, not roots. Write
parent[root_u] = root_v. Writingparent[u] = root_vcan leave a group split. - No path halving. The answer is the same, but each
findcan walk a long chain. - Using it for a path. An MST does not give the cheapest path between two nodes. Use Dijkstra for that.
Practice
Builds on Union-Find, which you haven’t finished yet.
Minimum Spanning Tree (Kruskal's, built on Union-Find)
There are n cities, labeled 1 to n. Each connections[i] = [xi, yi, cost_i] says you can build a two-way link between city xi and city yi for cost_i.
Choose links so that every city can reach every other city through built links, and pay as little as possible in total. Return that smallest total, or -1 if even building every link leaves some cities cut off.
2-3 for 1 and 1-2 for 5.Kruskal's MST
edge list sorted by weight ➔ union by rank/size ➔ connect components- You need the cheapest route from one source to the other nodes, as in Network Delay Time (LC 743), not the cheapest set of edges that joins everything. See Dijkstra
| 1 | from typing import List |
| 2 | |
| 3 | def kruskal_mst(n: int, edges: List[List[int]]) -> int: |
| 4 | """Kruskal's MST (Connecting Cities With Minimum Cost): cheapest total cost to join |
| 5 | nodes 1..n, or -1. |
| 6 | Time: O(E log E) | Space: O(V) |
| 7 | """ |
| 8 | parent = list(range(n + 1)) |
| 9 | |
| 10 | def find(x: int) -> int: |
| 11 | while parent[x] != x: |
| 12 | parent[x] = parent[parent[x]] # Path halving: skip a level on every step |
| 13 | x = parent[x] |
| 14 | return x |
| 15 | |
| 16 | edges.sort(key=lambda e: e[2]) # Cheapest edges first |
| 17 | mst_cost = 0 |
| 18 | edges_count = 0 |
| 19 | |
| 20 | for u, v, w in edges: |
| 21 | root_u, root_v = find(u), find(v) |
| 22 | if root_u != root_v: # Different groups: this edge is safe to take |
| 23 | parent[root_u] = root_v # Join the roots, not the nodes |
| 24 | mst_cost += w |
| 25 | edges_count += 1 |
| 26 | if edges_count == n - 1: |
| 27 | break # A spanning tree has exactly n - 1 edges |
| 28 | |
| 29 | return mst_cost if edges_count == n - 1 else -1 # Fewer edges: not connected |
find gives one root to exactly the nodes they connect.Sort edges by weight and take each edge whose ends have different roots, find(u) != find(v), joining the two groups. The cheapest edge between two separate groups is always safe to take: any full wiring must cross that gap somewhere, and swapping in the cheaper edge never costs more; an edge whose ends already share a root would only close a cycle, so skipping it loses nothing. The trap is the final check: fewer than n - 1 edges taken means the graph is not connected, so return -1 instead of the partial cost.
See it run
Kruskal's minimum spanning tree, step by step
parent [1, 2, 3, 4]mst_cost 0edges_count 0
Each line is a road with its cost beside it. A node shows its number, a slash, then its root. The row under the graph is edges sorted by weight, written as u-v:cost.
testthe edge being checked, and its two end nodestakean edge added to the treeskipan edge whose ends already share a root
edges.sort puts the cheapest edge first. Every node is its own root, so the groups are 4 single nodes.
Gotcha 1 of 4
- The trap
Gotcha 1: Returning
mst_costwithout checkingedges_countMistakereturn mst_costFixreturn mst_cost if edges_count == n - 1 else -1What happens: A tree that joins
nnodes has exactlyn - 1edges. If the edges run out with fewer, some cities are still in separate groups.mst_costis then the cost of a partial wiring. The problem asks for-1in that case.Example: Connecting Cities With Minimum Cost (LC 1135): n = 4, connections = [[1, 2, 3], [3, 4, 4]]Mistake: returns 7Fix: returns -1
Deep Dive
Why the cheapest edge between two groups is safe
A spanning tree joins all n nodes with n - 1 edges and no cycle. We want the one with the lowest total cost.
At any moment find splits the nodes into groups. Take the cheapest edge e that joins two different groups. Look at any full wiring that does not use e. That wiring must connect the two groups somewhere, so it has some edge f that crosses between them. Now remove f and add e. The wiring is still connected, and its cost did not go up, because e is no more expensive than f.
So some cheapest wiring uses e. Taking e never rules out a cheapest wiring, and the same argument holds after every join.
An edge whose two ends share a root is different. Both ends are already connected, so the edge only closes a cycle. Skipping it loses nothing.
One trace: an edge taken and an edge skipped
The board runs kruskal_mst on n = 4 and connections = [[1, 2, 6], [2, 3, 1], [2, 4, 3], [3, 4, 4]]. After the sort the order is 2-3:1, 2-4:3, 3-4:4 and 1-2:6.
Edge 2-3 has roots 2 and 3, which differ, so it is taken and parent[2] = 3. Edge 2-4 has roots 3 and 4, so it is taken and parent[3] = 4. Now nodes 2, 3 and 4 share root 4.
Edge 3-4 has root 4 on both ends. Taking it would close the triangle 2-3-4, so it is skipped. This is the step marked as skipped on the board.
Edge 1-2 has roots 1 and 4, so it is taken, and edges_count reaches n - 1 = 3. The cost is 1 + 3 + 6 = 10. The loop stops at once.
The trap: a graph that is not connected
The loop ends when edges_count is n - 1, or when the edges run out. If the edges run out first, some nodes are in separate groups, and no wiring can join them all.
Example: Connecting Cities With Minimum Cost (LC 1135) with n = 4 and connections = [[1, 2, 3], [3, 4, 4]]. Both edges are taken, so mst_cost is 7 and edges_count is 2. But n - 1 is 3. The cities 1 and 2 never join the cities 3 and 4. The right answer is -1, and return mst_cost would return 7.
The other trap is the join itself. parent[root_u] = root_v links the roots. Writing parent[u] = root_v moves only u, so a group can look split. For the graph in the trace, that mistake returns 8 and not 10.
The cost, and how it differs from Dijkstra
The sort costs O(E log E). Each find with path halving is close to constant. So the total is O(E log E) time, and parent takes O(V) space.
Min Cost to Connect All Points (LC 1584) has no edge list. Every pair of points is an edge, so 1000 points give 499500 edges. Build them all, and then run the same loop.
Dijkstra (the cheapest-first card) and this card both pick cheap edges, but they answer different questions. Dijkstra finds the cheapest route from one source to each node. Kruskal finds the cheapest set of edges that joins all nodes.
Example: take edges 1-2:2, 2-3:2 and 1-3:3. The cheapest wiring uses 1-2 and 2-3, and costs 4. The cheapest routes from node 1 use 1-2 and 1-3, because node 3 is cheapest to reach directly. Those two edges cost 5.
60-Second Pitch
"I need the cheapest set of edges that joins every node, so I use Kruskal's algorithm with Union-Find. I sort the edges by weight. For each edge, I check whether its two ends already have the same root. If the roots differ, this is the cheapest edge between two groups, so I link the roots and add its weight. If the roots are equal, the edge would close a cycle, so I skip it. This is safe because any full wiring must cross between two groups somewhere, and swapping in the cheaper edge never raises the cost. I stop at n - 1 edges. If I run out of edges before that, the graph is not connected and I return -1. The time is O(E log E) for the sort."
Common Questions
- Why does taking the cheapest edge between two groups never hurt?
Any full wiring must cross between those two groups with some edge. Replace that edge with the cheapest one. The wiring stays connected and costs no more. So a cheapest wiring that uses the edge always exists.
- What are the time and space complexity?
O(E log E) time for the sort. The loop makes E calls to
find, each close to constant with path halving. The space is O(V) forparent. For Min Cost to Connect All Points (LC 1584), E is about V squared divided by 2.- How do you know the graph is not connected?
A spanning tree has exactly
n - 1edges. If the loop ends withedges_countbelown - 1, some nodes are in separate groups. Return -1.- Kruskal or Prim: which would you pick?
Kruskal is short when the input is an edge list, because it needs only a sort and Union-Find. Prim grows one tree with a heap, and it suits a dense graph given as a matrix. Both find a minimum spanning tree.
- Is the minimum spanning tree unique?
Not always. If two edges have the same weight, two different trees can have the same lowest cost. The total cost is always the same. Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree (LC 1489) asks which edges are in every tree.
SWE Reasoning
Spot it
- The task is to connect all points, cities, computers or pipes at the lowest total cost.
- The answer is one total cost, not a path between two nodes.
- The input is a list of weighted edges, or every pair of points can be an edge.
- The wiring needs no cycle, because a cycle only repeats a link that already exists.
- The statement says to return -1 or false when the nodes cannot all be joined.
The invariant, step by step
parentstarts with every node as its own root, so every node is its own group.mst_costandedges_countare 0.edges.sortputs the cheapest edge first.- For each edge, compute
find(u)andfind(v). - If the roots differ, this is the cheapest edge left between two groups. Link the roots, add
wtomst_costand add 1 toedges_count. - If the roots are equal, the ends are already connected. Skip the edge.
- Stop when
edges_count == n - 1. If the edges run out first, return -1.
Traps
- No final check. Returning
mst_costwhenedges_countis belown - 1gives the cost of a partial wiring. Return -1. - Sorting by the wrong field. The weight is
e[2]. Sorting by a city number breaks the cheapest-edge rule. - Linking nodes, not roots. Write
parent[root_u] = root_v. Writingparent[u] = root_vcan leave a group split. - No path halving. The answer is the same, but each
findcan walk a long chain. - Using it for a path. An MST does not give the cheapest path between two nodes. Use Dijkstra for that.