Connecting Cities With Minimum Cost

For this problem, we can use Kruskal’s algorithm to find the minimum spanning tree (MST) of the graph that represents the cities and connections. A minimum spanning tree is a subset of the edges that forms a tree that includes every vertex, where the sum of the weights of the edges in the tree is minimized.

The solution will follow these steps:

Sort the connections by their cost.
Use Union-Find (Disjoint Set Union) to connect the cities, starting with the smallest cost connections.
Keep track of the total cost and the number of cities connected.
If the number of connected cities reaches n, return the total cost. Otherwise, return -1 if connecting all cities is impossible.

Below is the implementation:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution:
    def minimumCost(self, n: int, connections: List[List[int]]) -> int:
        # A function to find the root of a city in a disjoint set
        def find(x):
            if x != parent[x]:
                parent[x] = find(parent[x])
            return parent[x]

        # Sorting the connections by cost
        connections.sort(key=lambda x: x[2])

        # Initialize parent array for Union-Find
        parent = [i for i in range(n + 1)]

        cost = 0
        edges = 0

        # Iterate through the connections
        for x, y, c in connections:
            root_x = find(x)
            root_y = find(y)

            # If the cities are not connected, union them and update the cost
            if root_x != root_y:
                parent[root_y] = root_x
                cost += c
                edges += 1

                # If all cities are connected, return the cost
                if edges == n - 1:
                    return cost

        # If it's impossible to connect all cities, return -1
        return -1

The function find is a helper function to find the root of a city using a path compression technique. It is part of the Union-Find algorithm.