Connecting Cities With Minimum Cost

Problem Statement

In the given scenario, there are n cities that are identified by labels ranging from 1 to n. The task is to determine the minimum cost required to connect all these cities. The inter-city connections and their associated costs are specified in an array, connections, with each element formatted as [xi, yi, costi]. This notation indicates that there is a bi-directional link between cities xi and yi with an associated connection cost of costi.

The main objective is to find the least expensive way to establish connections between the cities such that every city can be reached from any other city. If it is impossible to ensure that all cities are interconnected due to limitations in the connections provided, the function should return -1. Here, the result should not just be the aggregation of provided connection costs but the minimal summed cost that ensures all cities are interconnected.

Examples

Example 1

Input:

n = 3, connections = [[1,2,5],[1,3,6],[2,3,1]]

Output:

6

Explanation:

Choosing any 2 edges will connect all cities so we choose the minimum 2.

Example 2

Input:

n = 4, connections = [[1,2,3],[3,4,4]]

Output:

-1

Explanation:

There is no way to connect all cities even if all edges are used.

Constraints

• 1 <= n <= 104
• 1 <= connections.length <= 104
• connections[i].length == 3
• 1 <= xi, yi <= n
• xi != yi
• 0 <= costi <= 105

Approach and Intuition

Given the problem's nature, the key is to connect the cities with the minimal cost ensuring that any city can be reached from any other. This presents a clear use-case for the Minimum Spanning Tree (MST) algorithms such as Kruskal's or Prim's algorithm, where:

1. Modeling the Cities and Connections: Think of cities as nodes and the connections with costs as weighted edges in a graph.

2. Utilizing Kruskal's Algorithm: Sort all the edges based on their weights (costs) and start adding them to the MST, ensuring no cycles are formed using a Union-Find structure until n-1 edges are added or all connections are processed.

   • If you manage to add n-1 edges and connect all cities, the total cost of these edges is your answer.
   • If you finish all connections and some cities remain unconnected, it's impossible to connect all cities, hence return -1.

3. Using Prim's Algorithm: Start from any city and keep adding the least expensive outward edge to the MST that doesn't form a cycle, until all cities are connected.

   • Similar to Kruskal's, if you connect all cities, the total cost of the edges used will be your answer.
   • If you run out of viable connections before connecting all cities, return -1.

Examples Review:

• In the first example, you can see that connecting the cities through any two connections amongst the three options provided necessarily includes the connection with the lowest cost, which gives a total minimized cost.
• The second example illustrates a scenario where not all cities can be connected even if all provided connections are utilized, resulting in a return value of -1.

The choice of algorithm (Kruskal’s vs Prim’s) can depend on the specifics of the implementation and the nature of the input data (e.g., density of the graph), but both fundamentally serve to find the minimum spanning tree which is crucial for solving this problem.

Solutions

class UnionFind {
private:
    vector<int> rank; // Rank based on the size of each component
    vector<int> parent; // To store the parent of each element
    
public:
    void merge(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX == rootY) return;
    
        if (this->rank[rootX] > this->rank[rootY]) {
            this->parent[rootY] = rootX;
            this->rank[rootX] += this->rank[rootY];
        } else {
            this->parent[rootX] = rootY;
            this->rank[rootY] += this->rank[rootX];
        }
    }
    
    int find(int x) {
        while (x != this->parent[x]) {
            this->parent[x] = this->parent[parent[x]];
            x = this->parent[x];
        }
        return x;
    }
    
    bool connected(int x, int y) {
        return find(x) == find(y);
    }
    
    UnionFind(int N) {
        this->parent.resize(N + 1);
        this->rank.resize(N + 1);
        for (int i = 1; i <= N; ++i) {
            this->parent[i] = i;
            this->rank[i] = 1;
        }
    }
};
    
class Solution {
public:
    int minimumCost(int N, vector<vector<int>>& connections) {
        UnionFind *uf = new UnionFind(N);
        sort(connections.begin(), connections.end(),
            [](const vector<int> &a, const vector<int> &b) {
                return a[2] < b[2];
            });
    
        int mst_edges = 0;
        int mst_cost = 0;
        for (const auto &edge : connections) {
            int a = edge[0];
            int b = edge[1];
            if (!uf->connected(a, b)) {
                uf->merge(a, b);
                mst_cost += edge[2];
                mst_edges++;
            }
        }
    
        if (mst_edges == N - 1) {
            return mst_cost;
        } else {
            return -1;
        }
    }
};