Domain 2MediumMEDIUM

Connecting Cities With Minimum Cost

Find the minimum cost to connect all cities using Kruskal's algorithm and Union-Find, returning -1 if disconnected.

Domain: medium•Updated: 2026-09-09
#Kruskal's Algorithm#Union-Find (DSU)#$O(M log M)$ time complexity#$O(N + M)$ space complexity

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 (1≤N≤100001 \le N \le 10000). Cities are numbered 11 to NN.
  • 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.
  • -1 if 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:

  1. 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.
  2. 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.
  3. If after considering all available edges, there are still multiple disconnected components (i.e., fewer than N−1N-1 successful unions), it is impossible to connect all cities.

Approach

  1. Handle Trivial Case: If N == 1, the cost is 0 since a single city requires no connections. Return immediately.
  2. 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 (N−1N-1).
  3. Sort Edges: Sort connections based on cost in ascending order. This is O(Mlog⁡M)O(M \log M).
  4. 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 (N−1N-1).
    • If roots are same, skip (cycle detected or already connected component).
  5. Early Termination: Stop iterating if we have successfully performed N−1N-1 unions (components_count == 0), as the MST is complete.
  6. 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: O(Mlog⁡M)O(M \log M) where MM is the number of connections. The dominant factor is sorting the edges (O(Mlog⁡M)O(M \log M)). DSU operations take nearly constant time on average due to path compression and union by rank, roughly O(α(N))O(\alpha(N)). Thus total processing is dominated by sorting: O(Mlog⁡M)O(M \log M).
  • Space Complexity: O(N+M)O(N + M). We need O(N)O(N) space for the DSU parent/rank arrays. Sorting edges might take auxiliary space depending on implementation (often in-place or O(1)O(1) extra), but generally considered within limits (O(M)O(M)).

Edge Cases Handled

  • Single City (N = 1): The code explicitly checks if N == 1 and 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 N−1N-1 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 connections is empty and N > 1, the loop doesn’t run, count remains >0>0, returns -1 correctly. If N=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 (N×Costmax≈109N \times Cost_{max} \approx 10^9).

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