Minimize maximum component cost

Binary Search Union-Find Graph Theory Sorting

43.4% acceptance

Feb 25, 2026

116

You are given an undirected connected graph with n nodes labeled from 0 to n - 1 and a 2D integer array edges where edges[i] = [ui, vi, wi] denotes an undirected edge between node ui and node vi with weight wi, and an integer k. You are allowed to remove any number of edges from the graph such that the resulting graph has at most k connected components. The cost of a component is defined as the maximum edge weight in that component. If a component has no edges, its cost is 0. Return the minimum possible value of the maximum cost among all components after such removals.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn min_cost(n: i32, edges: Vec<Vec<i32>>, k: i32) -> i32 {
    let n = n as usize;
    let k = k as i32;
    if n as i32 <= k { return 0; }

    let mut sorted = edges.clone();
    sorted.sort_unstable_by_key(|e| e[2]);

    let mut parent: Vec<usize> = (0..n).collect();
    let mut rank = vec![0usize; n];

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

    let mut comps = n as i32;
    let mut i = 0;
    while i < sorted.len() {
      let w = sorted[i][2];
      while i < sorted.len() && sorted[i][2] == w {
        let u = sorted[i][0] as usize;
        let v = sorted[i][1] as usize;
        let ru = find(&mut parent, u);
        let rv = find(&mut parent, v);
        if ru != rv {
          if rank[ru] < rank[rv] {
            parent[ru] = rv;
          } else if rank[ru] > rank[rv] {
            parent[rv] = ru;
          } else {
            parent[rv] = ru;
            rank[ru] += 1;
          }
          comps -= 1;
        }
        i += 1;
      }
      if comps <= k { return w; }
    }
    0
  }
}