Problem Breakdown
We are given N cities (nodes) and a list of weighted edges (connections). The goal is to connect all cities into a single component with the minimum total cost. This defines the Minimum Spanning Tree (MST) problem on an undirected graph. If it’s impossible to form such a tree because the graph is disconnected, we must return -1.
Inputs:
N: Integer representing number of cities (). Cities are numbered to .connections: List of[u, v, cost]tuples. Each represents an undirected edge with weight.
Outputs:
- Minimum total integer cost if all cities can be connected.
-1if the graph is disconnected (cannot connect all nodes).
Intuition
To minimize the sum of connection costs while ensuring connectivity, we should greedily select edges that offer the lowest possible cost without forming cycles. This greedy strategy aligns with Kruskal’s Algorithm.
The key insight is:
- If an edge connects two previously disconnected components (checked via Union-Find), it contributes to the MST and reduces the number of connected components by one.
- We should process edges in increasing order of cost. This ensures we always pick the cheapest valid connection first, satisfying the cut property for MSTs.
- If after considering all available edges, there are still multiple disconnected components (i.e., fewer than successful unions), it is impossible to connect all cities.
Approach
- Handle Trivial Case: If
N == 1, the cost is 0 since a single city requires no connections. Return immediately. - Initialize Union-Find (DSU): Create a data structure where each node points to itself initially. We will use path compression and union by rank/size for efficiency. Track the number of successful unions needed ().
- Sort Edges: Sort
connectionsbased on cost in ascending order. This is . - Iterate & Union: Loop through sorted edges:
- Find roots of both cities involved in the edge.
- If roots differ, union them (merge sets), add cost to total, and decrement a counter tracking remaining needed unions ().
- If roots are same, skip (cycle detected or already connected component).
- Early Termination: Stop iterating if we have successfully performed unions (
components_count == 0), as the MST is complete. - Final Check: After loop finishes, check
components_count. If it remains greater than 0 (meaning not all nodes merged into one component), return-1. Otherwise, return accumulated cost.
Complexity Analysis
- Time Complexity: where is the number of connections. The dominant factor is sorting the edges (). DSU operations take nearly constant time on average due to path compression and union by rank, roughly . Thus total processing is dominated by sorting: .
- Space Complexity: . We need space for the DSU parent/rank arrays. Sorting edges might take auxiliary space depending on implementation (often in-place or extra), but generally considered within limits ().
Edge Cases Handled
- Single City (
N = 1): The code explicitly checksif N == 1and returns 0 immediately. No edges are needed to connect a single node, so cost is 0. - Disconnected Graph: If the loop finishes and we haven’t performed unions (i.e.,
components_count > 0), it implies some cities remain isolated even after using all available connections. We return-1. - Empty Connections List: The sort handles an empty list gracefully. If
connectionsis empty andN > 1, the loop doesn’t run, count remains , returns -1 correctly. IfN=1, it returns 0. - Cycle Detection: The DSU logic checks if roots differ before unioning. This prevents cycles from being added to the cost sum.
- Large Costs / Overflow: Python handles large integers automatically; sums fit within standard integer limits for this problem’s constraints ().
Solution
class UnionFind:
def __init__(self, n):
self.parent = list(range(n + 1)) # Cities are 1-indexed (indices 0 to N)
self.rank = [0] * (n + 1) # Initialize rank for union by size/rank
def find(self, x):
root = x
while root != self.parent[root]:
root = self.parent[root]
# Path compression: make all nodes on path point directly to root
curr = x
while curr != root:
nxt = self.parent[curr]
self.parent[curr] = root
curr = nxt
return root
def union(self, x, y):
rootX = self.find(x)
rootY = self.find(y)
if rootX == rootY:
return False # Already connected
# Union by rank to keep tree height small (O(log N))
if self.rank[rootX] < self.rank[rootY]:
self.parent[rootX] = rootY
elif self.rank[rootX] > self.rank[rootY]:
self.parent[rootY] = rootX
else:
self.parent[rootY] = rootX
self.rank[rootX] += 1
return True
def minCost(N, connections):
# Handle single city case explicitly
if N == 1:
return 0
uf = UnionFind(N)
# Sort edges by cost ascending (Kruskal's greedy step)
connections.sort(key=lambda x: x[2])
total_cost = 0
components_count = N - 1 # We need to reduce component count from N-1 merges
for u, v, cost in connections:
if uf.union(u, v):
total_cost += cost
components_count -= 1
# Optimization: If we have connected all cities (N-1 edges added), stop early.
if components_count == 0:
break
return -1 if components_count > 0 else total_cost
# Example usage matching LeetCode signature logic implicitly handled above