3613. Minimize Maximum Component Cost Medium

1/**
2 * [3613] Minimize Maximum Component Cost
3 *
4 * <p data-end="331" data-start="85">You are given an undirected connected graph with <code data-end="137" data-start="134">n nodes labeled from 0 to <code data-end="171" data-start="164">n - 1 and a 2D integer array <code data-end="202" data-start="195">edges where <code data-end="234" data-start="209">edges[i] = [ui, vi, wi] denotes an undirected edge between node <code data-end="279" data-start="275">ui and node <code data-end="293" data-start="289">vi with weight <code data-end="310" data-start="306">wi, and an integer <code data-end="330" data-start="327">k.
5 * <p data-end="461" data-start="333">You are allowed to remove any number of edges from the graph such that the resulting graph has at most <code data-end="439" data-start="436">k connected components.
6 * <p data-end="589" data-start="463">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.
7 * <p data-end="760" data-start="661">Return the minimum possible value of the maximum cost among all components <strong data-end="759" data-start="736">after such removals.
8 *  
9 * <strong class="example">Example 1:
10 * <div class="example-block">
11 * Input: <span class="example-io">n = 5, edges = [[0,1,4],[1,2,3],[1,3,2],[3,4,6]], k = 2</span>
12 * Output: <span class="example-io">4</span>
13 * Explanation:
14 * <img alt="" src="https://assets.leetcode.com/uploads/2025/04/19/minimizemaximumm.jpg" style="width: 535px; height: 225px;" />
15 * 
16 * 	<li data-end="1070" data-start="1021">Remove the edge between nodes 3 and 4 (weight 6).
17 * 	<li data-end="1141" data-start="1073">The resulting components have costs of 0 and 4, so the overall maximum cost is 4.
18 * </div>
19 * <strong class="example">Example 2:
20 * <div class="example-block">
21 * Input: <span class="example-io">n = 4, edges = [[0,1,5],[1,2,5],[2,3,5]], k = 1</span>
22 * Output: <span class="example-io">5</span>
23 * Explanation:
24 * <img alt="" src="https://assets.leetcode.com/uploads/2025/04/19/minmax2.jpg" style="width: 315px; height: 55px;" />
25 * 
26 * 	<li data-end="1315" data-start="1251">No edge can be removed, since allowing only one component (k = 1) requires the graph to stay fully connected.
27 * 	<li data-end="1389" data-start="1318">That single component&rsquo;s cost equals its largest edge weight, which is 5.
28 * </div>
29 *  
30 * Constraints:
31 * 
32 * 	1 <= n <= 5 * 10^4
33 * 	0 <= edges.length <= 10^5
34 * 	edges[i].length == 3
35 * 	0 <= ui, vi < n
36 * 	1 <= wi <= 10^6
37 * 	1 <= k <= n
38 * 	The input graph is connected.
39 * 
40 */
41pub struct Solution {}
42
43// problem: https://leetcode.com/problems/minimize-maximum-component-cost/
44// discuss: https://leetcode.com/problems/minimize-maximum-component-cost/discuss/?currentPage=1&orderBy=most_votes&query=
45
46// submission codes start here
47
48impl Solution {
49    pub fn min_cost(n: i32, edges: Vec<Vec<i32>>, k: i32) -> i32 {
50        0
51    }
52}
53
54// submission codes end
55
56#[cfg(test)]
57mod tests {
58    use super::*;
59
60    #[test]
61    fn test_3613() {
62    }
63}
64