Minimum time for k connected components

Binary Search Union-Find Graph Theory Sorting

45.2% acceptance

Feb 25, 2026

124

You are given an integer n and an undirected graph with n nodes labeled from 0 to n - 1. This is represented by a 2D array edges, where edges[i] = [ui, vi, timei] indicates an undirected edge between nodes ui and vi that can be removed at timei. You are also given an integer k. Initially, the graph may be connected or disconnected. Your task is to find the minimum time t such that after removing all edges with time <= t, the graph contains at least k connected components. Return the minimum time t. A connected component is a subgraph of a graph in which there exists a path between any two vertices, and no vertex of the subgraph shares an edge with a vertex outside of the subgraph.

Solution

Rust

Time O(n log n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn min_time(n: i32, edges: Vec<Vec<i32>>, k: i32) -> i32 {
    let n = n as usize;
    let k = k as usize;
    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
    }

    // Build maximum spanning forest using edges sorted descending by time.
    // This ensures any non-tree edge has time <= the minimum tree-edge time
    // on the path between its endpoints, so all non-tree edges are already
    // removed when we reach the relevant tree-edge threshold.
    let mut forest_times: Vec<i32> = Vec::new();
    let mut sorted_edges = edges.clone();
    sorted_edges.sort_unstable_by(|a, b| b[2].cmp(&a[2]));

    for e in &sorted_edges {
      let (u, v) = (e[0] as usize, e[1] as usize);
      let ru = find(&mut parent, u);
      let rv = find(&mut parent, v);
      if ru != rv {
        forest_times.push(e[2]);
        if rank[ru] < rank[rv] {
          parent[ru] = rv;
        } else if rank[ru] > rank[rv] {
          parent[rv] = ru;
        } else {
          parent[rv] = ru;
          rank[ru] += 1;
        }
      }
    }

    // initial_comps = n - spanning forest edges
    let initial_comps = n - forest_times.len();
    if initial_comps >= k {
      return 0;
    }
    // Need (k - initial_comps) spanning tree edges to be removed
    let need = k - initial_comps;
    // forest_times was collected in descending order; sort ascending
    // to pick the need-th smallest tree edge as the answer threshold.
    forest_times.sort_unstable();
    forest_times[need - 1]
  }
}