Connecting cities with minimum cost

Union-Find Graph Theory Heap (Priority Queue) Minimum Spanning Tree

63.5% acceptance

Mar 31, 2026

1174

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.

Solution

Rust

Time O(2^n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn minimum_cost(n: i32, mut connections: Vec<Vec<i32>>) -> i32 {
    connections.sort_unstable_by_key(|c| c[2]);
    let n = n as usize;
    let mut parent: Vec<usize> = (0..=n).collect();
    let mut rank = vec![0u8; n + 1];
    let mut components = n;
    let mut cost = 0;

    fn find(parent: &mut Vec<usize>, x: usize) -> usize {
      if parent[x] != x {
        parent[x] = find(parent, parent[x]);
      }
      parent[x]
    }

    for c in &connections {
      let (a, b, w) = (c[0] as usize, c[1] as usize, c[2]);
      let ra = find(&mut parent, a);
      let rb = find(&mut parent, b);
      if ra != rb {
        if rank[ra] < rank[rb] {
          parent[ra] = rb;
        } else if rank[ra] > rank[rb] {
          parent[rb] = ra;
        } else {
          parent[rb] = ra;
          rank[ra] += 1;
        }
        cost += w;
        components -= 1;
        if components == 1 {
          return cost;
        }
      }
    }
    if components == 1 { cost } else { -1 }
  }
}