Connecting Cities With Minimum Cost

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;
        }
    }
};

The provided C++ code offers a solution to the problem of connecting cities with the minimum cost using a graph-based approach. This solution employs Kruskal’s algorithm with the help of a Union-Find data structure to form a Minimum Spanning Tree (MST). Below is a breakdown of how the solution works:

• The UnionFind class is used to handle the union and find operations efficiently. It maintains two arrays: parent and rank, where parent keeps track of the direct parent node of each node, and rank helps in keeping the tree as flat as possible when merging two trees. This class provides methods such as merge for combining two subsets, find for finding the root of an element (with path compression), and connected to check if two elements are in the same set.

• The Solution class contains the minimumCost method which takes the number of cities N and a list of connections. Each connection is represented as a vector containing two cities and the cost to connect them (e.g., [city1, city2, cost]).

  1. Initialize a new UnionFind instance for N cities.
  2. Sort the connections based on the costs in ascending order to consider cheaper connections first, aiding in finding the minimum cost.
  3. Traverse through the sorted connections and use the Union-Find structure to add connections to the MST if they do not form a cycle (checked using the connected method).
  4. Sum up the costs of the connections added to the MST.
  5. Check if the number of edges in the MST is exactly N-1 (a characteristic of an MST in a connected graph). If yes, return the total cost. Otherwise, return -1 to signify that connecting all cities at the minimum cost is not possible.

This algorithm is efficient in terms of time complexity, primarily due to the use of path compression and union by rank in the Union-Find implementation, and it ensures that the minimum cost spanning tree covers all cities if possible.

class UnionFind {
    private int[] rank; // Rank for each node
    private int[] parent;

    public UnionFind(int size) {
        this.rank = new int[size + 1];
        this.parent = new int[size + 1];
        for (int i = 1; i <= size; ++i) {
            this.parent[i] = i;
            this.rank[i] = 1;
        }
    }

    public int find(int x) {
        while (x != this.parent[x]) {
            this.parent[x] = this.parent[parent[x]]; // Path compression
            x = this.parent[x];
        }
        return x;
    }

    public void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            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];
            }
        }
    }

    public boolean connected(int x, int y) {
        return find(x) == find(y);
    }
}

class GraphSolution {
    public int minCost(int nodeCount, int[][] connections) {
        UnionFind uf = new UnionFind(nodeCount);
        Arrays.sort(connections, (a, b) -> Integer.compare(a[2], b[2]));
        int mstCost = 0, edgesUsed = 0;
        for (int[] connection : connections) {
            int node1 = connection[0], node2 = connection[1], cost = connection[2];
            if (!uf.connected(node1, node2)) {
                uf.union(node1, node2);
                mstCost += cost;
                edgesUsed++;
            }
        }
        return edgesUsed == nodeCount - 1 ? mstCost : -1; // Check if all nodes were connected
    }
}

The Java solution provided addresses the problem of connecting cities with a minimum cost using a variation of Kruskal's algorithm, utilizing a Union-Find data structure to form the minimum spanning tree (MST).

Structure of the Solution:

• Union-Find Class: This class handles the disjoint sets operations. It uses path compression in its find function to optimize the time complexity of finding the root of each node. The union method merges two subsets based on rank, ensuring that tree height is minimized to keep subsequent operations efficient.

• GraphSolution Class: This class contains the method minCost which performs the core logic to calculate the minimum cost needed to connect all cities (nodes):

  • Initialization: Creates an instance of the UnionFind class sized to the given number of nodes.
  • Sorting Connections: The connections array is sorted based on cost to facilitate the greedy approach of Kruskal's algorithm.
  • Processing Connections: It iteratively tries to form the MST by including the cheapest edges first and using the union-find structure to detect and avoid cycles. If an edge connection does not form a cycle, it is added to the MST, and its cost is accumulated into mstCost.
  • Final Check: After processing all connections, checks if the number of edges used equals nodeCount - 1, which verifies that all nodes are connected. If not, it returns -1, indicating that not all cities can be connected; otherwise, it returns the total minimum cost.

This approach ensures that the solution is not only efficient but also adheres to the constraints typical of MST problems—primarily minimizing the total edge cost while ensuring all nodes are included without any cycles. The provided Java code effectively implements this strategy using well-known and robust algorithms in computational theory.