Problem Description

There are N cities numbered from 1 to N. You are given some connections among the cities. Each connection is represented as an array of three elements [city1, city2, cost], which indicates that city1 and city2 can be connected directly and the cost of this connection is cost. Note that the connection is bidirectional so connecting city1 to city2 is the same as connecting city2 to city1.

Now, the goal is to come up with a plan that connects all cities with minimum total cost. In other words, for every pair of cities, there should be a path of connections that connect those two cities together and the sum of the connection costs used should be minimum.

If it is impossible to connect all cities, the function should return -1.

Example

Consider an example where there are 3 cities and the connections among them are as follows:

1 1 - 2 with cost 5
2 1 - 3 with cost 6
3 2 - 3 with cost 1

We can connect all three cities with total cost 6 if we choose the connections 1-2 and 2-3.

Approach

The problem asks for the minimum cost to connect all cities together, which is essentially asking for a minimum spanning tree in the graph theory. A minimum spanning tree of a graph is a tree that spans all the vertices in the graph and has the minimum total edge weight.

We can use Kruskal’s algorithm to find the minimum spanning tree. Here is the basic idea of Kruskal's algorithm:

1. Sort all the edges in the graph in non-decreasing order of their cost.
2. Start adding edges to the MST from the edge with the smallest cost.
3. Add an edge only if it doesn't form a cycle with the MST formed so far.
4. Repeat steps #2 and #3 until there are (V - 1) edges in the spanning tree (V is the number of vertices in the graph).

To detect cycles, we can use Union-Find algorithm. Union-Find algorithm is a very efficient algorithm to perform the following two operations: joined(a, b) (“are a and b in the same set?”) and join(a, b) (“put a and b into the same set”).

Coding solutions

Python Solution

1
2python
3class UnionFind:
4    def __init__(self):
5        self.parent = {}
6        
7    def union(self, x, y):
8        self.parent[self.find(x)] = self.find(y)
9        
10    def find(self, x):
11        path = []
12        while x != self.parent[x]:
13            path.append(x)
14            x = self.parent[x]
15        # compress the path leading back to the root
16        for node in path:
17            self.parent[node] = x
18        return x
19
20
21class Solution:
22    def minimumCost(self, N, connections):
23        uf = UnionFind()
24        # Initialize the parent pointer for each city
25        for i in range(1, N+1):
26            uf.parent[i] = i
27        # Sort the connections by their cost
28        connections.sort(key=lambda x: x[2])
29        res = 0
30        for city1, city2, cost in connections:
31            if uf.find(city1) != uf.find(city2):
32                uf.union(city1, city2)
33                res += cost
34        # Check if all cities are connected
35        root = uf.find(1)
36        for i in range(2, N+1):
37            if uf.find(i) != root:
38                return -1
39        return res

Java Solution

1
2java
3class Solution {
4    public int minimumCost(int N, int[][] connections) {
5        int[] parent = new int[N+1];
6        for (int i = 1; i <= N; i++)
7            parent[i] = i;
8        Arrays.sort(connections, (a, b) -> a[2] - b[2]);
9        int total = 0, edges = 0;
10        for (int[] conn : connections) {
11            int x = find(parent, conn[0]), y = find(parent, conn[1]);
12            if (x != y) {
13                parent[x] = y;
14                total += conn[2];
15                edges++;
16                if (edges == N-1)
17                    return total;
18            }
19        }
20        return -1;
21    }
22
23    private int find(int[] parent, int x) {
24        if (x != parent[x])
25            parent[x] = find(parent, parent[x]);
26        return parent[x];
27    }
28}

JavaScript Solution

1
2javascript
3class UnionFind {
4    constructor(N) {
5        this.parent = Array(N+1).fill(0).map((value, index) => index);
6    }
7
8    find(x) {
9        if (x !== this.parent[x]) {
10            this.parent[x] = this.find(this.parent[x]);
11        }
12        return this.parent[x];
13    }
14
15    union(x, y) {
16        this.parent[this.find(x)] = this.find(y);
17    }
18}
19
20var minimumCost = function(N, connections) {
21    const uf = new UnionFind(N);
22    connections.sort((a, b) => a[2] - b[2]);
23    let total = 0, edges = 0;
24    for (let conn of connections) {
25        let x = uf.find(conn[0]), y = uf.find(conn[1]);
26        if (x !== y) {
27            uf.union(x, y);
28            total += conn[2];
29            edges++;
30            if (edges === N-1)
31                return total;
32        }
33    }
34    return -1;
35};

C++ Solution

1
2cpp
3class Solution {
4public:
5    int minimumCost(int N, vector<vector<int>>& connections) {
6        vector<int> parent(N+1);
7        iota(parent.begin(), parent.end(), 0);
8        sort(connections.begin(), connections.end(), [](auto &a, auto &b){
9            return a[2] < b[2];
10        });
11        int total = 0, edges = 0;
12        for (auto &conn : connections) {
13            int x = find(parent, conn[0]), y = find(parent, conn[1]);
14            if (x != y) {
15                parent[x] = y;
16                total += conn[2];
17                edges++;
18                if (edges == N-1)
19                    return total;
20            }
21        }
22        return -1;
23    }
24    
25private:
26    int find(vector<int> &parent, int x) {
27        if (x != parent[x])
28            parent[x] = find(parent, parent[x]);
29        return parent[x];
30    }
31};

C# Solution

1
2csharp
3public class UnionFind
4{
5    private int[] parent;
6    public UnionFind(int n)
7    {
8        parent = new int[n+1];
9        for(int i=0; i<=n; i++) {
10            parent[i] = i;
11        }
12    }
13
14    public int Find(int x)
15    {
16        if(parent[x] != x) {
17            parent[x] = Find(parent[x]);
18        }
19        return parent[x];
20    }
21
22    public void Union(int x, int y)
23    {
24        parent[Find(x)] = Find(y);
25    }
26}
27
28public class Solution {
29    public int MinimumCost(int N, int[][] connections)
30    {
31        var uf = new UnionFind(N);
32        int totalCost = 0, edges = 0;
33        
34        Array.Sort(connections, (a, b) => a[2] - b[2]);
35        foreach (var connection in connections)
36        {
37            var city1 = uf.Find(connection[0]);
38            var city2 = uf.Find(connection[1]);
39            if (city1 != city2)
40            {
41                uf.Union(connection[0], connection[1]);
42                totalCost += connection[2];
43                edges++;
44            }
45            if (edges == N - 1) return totalCost;
46        }
47        return -1;
48    }
49}

The various implementations above provide a comprehensive solution to the problem of finding the minimum cost of connections among cities. Each of these solutions uses the Union-Find algorithm combined with Kruskal's algorithm to find the minimum spanning tree of the graph that represents the connections among the cities.

Each implementation first sorts the connections by cost in ascending order. After that, it iteratively constructs a minimum spanning tree by adding the cheapest possible edge that does not create a cycle. The cycle detection is efficiently performed by the Union-Find algorithm. If it is possible to connect all cities, the final total cost of the connections used is returned. Otherwise, the function returns -1.

These implementations exhibit excellent efficiency. They have a time complexity that is roughly proportional to E log E, where E is the number of edges in the graph (the number of given connections). This time complexity is due to the sorting of the edges and the use of the Union-Find algorithm which has almost linear time complexity.

The solutions also feature good space complexity, which is approximately O(N). The Union-Find data structure occupies linear space with respect to the number of vertices (cities).

In conclusion, these solutions efficiently solve the problem by combining the power of Union-Find and Kruskal's algorithms and effectively applying the concept of minimum spanning tree from graph theory.