1135. Connecting Cities With Minimum Cost

Published on April 24, 2023

Question

There are n cities labeled from 1 to n. You are given the integer n and an array connections where connections[i] = [xi, yi, costi] indicates that the cost of connecting city xi and city yi (bidirectional connection) is costi.

Return the minimum cost to connect all the n cities such that there is at least one path between each pair of cities. If it is impossible to connect all the n cities, return -1,

The cost is the sum of the connections' costs used.

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.

Algorithm

This is a typical question of finding the minimum spanning tree. Here we implement the Kruskal Algorithm.

For minimum spanning tree, we should find a tree without cycle and with least cost. In the question 261, we are asking to tell if a graph is a tree. So there are three main points:

Acyclic;
The graph has only one component after union;
Least cost.

Kruskal algorithm is utilizing the union find data structure. Unionfind could help us to identify cycle when processing the edges and after union all the nodes, we could get components count by calling count(). To get the least cost, we sort the edges by weight(cost), and processing by this order.

In the end, if there is only one component in the forest, we could return the calculated cost.

Code

class Solution {
    public int minimumCost(int n, int[][] connections) {
        int res = 0;
        if (connections == null || connections.length == 0 || connections[0] == null || connections[0].length == 0) {
            return -1;
        }
        UnionFind unionFind = new UnionFind(n + 1);
        Arrays.sort(connections, (a, b) -> (a[2] - b[2]));
        
        for (int[] connection : connections) {
            int v1 = connection[0];
            int v2 = connection[1];
            int cost = connection[2];
            if (unionFind.connected(v1, v2)) continue;
            unionFind.union(v1, v2);
            res += cost;
        }
        return unionFind.count == 2 ? res : -1;
    }
    
    class UnionFind {
        int[] parents;
        int count;
        
        public UnionFind(int n) {
            count = n;
            parents = new int[n];
            for (int i = 0; i < n; i++) {
                parents[i] = i;
            }
        }
        
        public int find(int x) {
            if (x != parents[x]) {
                parents[x] = find(parents[x]);
            }
            return parents[x];
        }
        
        public void union(int x, int y) {
            int xRoot = find(x);
            int yRoot = find(y);
            if (xRoot == yRoot) return;
            parents[yRoot] = xRoot;
            count--;
        }
        
        public int count() {
            return count;
        }
        
        public boolean connected(int x, int y) {
            return find(x) == find(y);
        }
    }
}

Code2

We have another algorithm: Prim's algorithm to solve this problem.

We need to construct a graph fist if necessary. Then choose a start node and put it to a priority queue. And then put the neighbors and edges to the PQ. By the nature of the PQ, one node with shortest edge (and the neighbor was not visited) was pop each time. After all the nodes was popped, we may get a MST.

class Solution {
    List<int[]>[] graph;
    public int minimumCost(int n, int[][] connections) {
        Prim prim = new Prim(n, connections);
        if (!prim.allConnected()) {
            return -1;
        }
        return prim.minDist;
        
    }
    
    class Prim {
        boolean[] visited;
        int[] minDists;
        int minDist;
        int[][] connections;
        int n;
        
        
        public Prim(int n, int[][] connections) {
            buildGraph(connections, n);
            this.connections = connections;
            this.n = n;
            visited = new boolean[n + 1];
            minDists = new int[n + 1];
            Arrays.fill(minDists, Integer.MAX_VALUE);
        
        
            PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> (a[2] - b[2]));
            for (int[] edge : graph[1]) {
                pq.offer(new int[]{0, edge[1], edge[2]});
            }
            minDists[1] = 0;
            minDist = 0;   
            visited[1] = true;
        
            while (!pq.isEmpty()) {
            int[] connection = pq.poll();
            int start = connection[0];
            int end = connection[1];
            int cost = connection[2];
            
            if (!visited[end]) {
                visited[end] = true;
                minDists[end] = cost;
                minDist += cost;
                for (int[] edge : graph[end]) {
                    if (!visited[edge[1]]) {
                        pq.offer(new int[]{end, edge[1], edge[2]});
                    }
                }
            }
            
        }
        }
        
        public boolean allConnected() {
            for (int i = 1; i <= n; i++) {
                if (!visited[i]) {
                    return false;
                }
            }
            return true;
        }
        
    }
    
    private void buildGraph(int[][] connections, int n) {
        graph = new List[n + 1];
        for (int i = 1; i <= n; i++) {
            graph[i] = new ArrayList<>();
        }
        for (int[] connection : connections) {
            int start = connection[0];
            int end = connection[1];
            int cost = connection[2];
            graph[start].add(new int[]{start, end, cost});
            graph[end].add(new int[]{end, start, cost});
        }
    }
}