3608. Minimum Time for K Connected Components Medium

1/**
2 * [3608] Minimum Time for K Connected Components
3 *
4 * 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.
5 * You are also given an integer k.
6 * 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.
7 * Return the minimum time t.
8 * 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.
9 *  
10 * <strong class="example">Example 1:
11 * <div class="example-block">
12 * Input: <span class="example-io">n = 2, edges = [[0,1,3]], k = 2</span>
13 * Output: <span class="example-io">3</span>
14 * Explanation:
15 * <img src="https://assets.leetcode.com/uploads/2025/05/31/screenshot-2025-06-01-at-022724.png" style="width: 230px; height: 85px;" />
16 * 
17 * 	Initially, there is one connected component {0, 1}.
18 * 	At time = 1 or 2, the graph remains unchanged.
19 * 	At time = 3, edge [0, 1] is removed, resulting in k = 2 connected components {0}, {1}. Thus, the answer is 3.
20 * </div>
21 * <strong class="example">Example 2:
22 * <div class="example-block">
23 * Input: <span class="example-io">n = 3, edges = [[0,1,2],[1,2,4]], k = 3</span>
24 * Output: <span class="example-io">4</span>
25 * Explanation:
26 * <img src="https://assets.leetcode.com/uploads/2025/05/31/screenshot-2025-06-01-at-022812.png" style="width: 180px; height: 164px;" />
27 * 
28 * 	Initially, there is one connected component {0, 1, 2}.
29 * 	At time = 2, edge [0, 1] is removed, resulting in two connected components {0}, {1, 2}.
30 * 	At time = 4, edge [1, 2] is removed, resulting in k = 3 connected components {0}, {1}, {2}. Thus, the answer is 4.
31 * </div>
32 * <strong class="example">Example 3:
33 * <div class="example-block">
34 * Input: <span class="example-io">n = 3, edges = [[0,2,5]], k = 2</span>
35 * Output: <span class="example-io">0</span>
36 * Explanation:
37 * <img src="https://assets.leetcode.com/uploads/2025/05/31/screenshot-2025-06-01-at-022930.png" style="width: 180px; height: 155px;" />
38 * 
39 * 	Since there are already k = 2 disconnected components {1}, {0, 2}, no edge removal is needed. Thus, the answer is 0.
40 * </div>
41 *  
42 * Constraints:
43 * 
44 * 	1 <= n <= 10^5
45 * 	0 <= edges.length <= 10^5
46 * 	edges[i] = [ui, vi, timei]
47 * 	0 <= ui, vi < n
48 * 	ui != vi
49 * 	1 <= timei <= 10^9
50 * 	1 <= k <= n
51 * 	There are no duplicate edges.
52 * 
53 */
54pub struct Solution {}
55
56// problem: https://leetcode.com/problems/minimum-time-for-k-connected-components/
57// discuss: https://leetcode.com/problems/minimum-time-for-k-connected-components/discuss/?currentPage=1&orderBy=most_votes&query=
58
59// submission codes start here
60
61impl Solution {
62    pub fn min_time(n: i32, edges: Vec<Vec<i32>>, k: i32) -> i32 {
63        0
64    }
65}
66
67// submission codes end
68
69#[cfg(test)]
70mod tests {
71    use super::*;
72
73    #[test]
74    fn test_3608() {
75    }
76}
77