LeetCode 题解工作台
包含 K 个连通分量需要的最小时间
给你一个整数 n ，表示一个包含 n 个节点（从 0 到 n - 1 编号）的无向图。该图由一个二维数组 edges 表示，其中 edges[i] = [u i , v i , time i ] 表示一条连接节点 u i 和节点 v i 的无向边，该边会在时间 time i 被移除。 Create …
4
题型
5
代码语言
3
相关题
当前训练重点
中等 · 二分·搜索·答案·空间
答案摘要
我们可以将边按时间从小到大排序，然后从时间最大的边开始依次将边加入图中，同时使用并查集维护当前图的连通分量数量。当连通分量数量小于 时，说明当前时间即为所求的最小时间。 时间复杂度 $O(n \times \alpha(n))$，空间复杂度 ，其中 是反阿克曼函数。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 二分·搜索·答案·空间 题型思路
题目描述
给你一个整数 n，表示一个包含 n 个节点（从 0 到 n - 1 编号）的无向图。该图由一个二维数组 edges 表示，其中 edges[i] = [ui, vi, timei] 表示一条连接节点 ui 和节点 vi 的无向边，该边会在时间 timei 被移除。
同时，另给你一个整数 k。
最初，图可能是连通的，也可能是非连通的。你的任务是找到一个 最小 的时间 t，使得在移除所有满足条件 time <= t 的边之后，该图包含 至少 k 个连通分量。
返回这个 最小 时间 t。
连通分量 是图的一个子图，其中任意两个顶点之间都存在路径，且子图中的任意顶点均不与子图外的顶点共享边。
示例 1：
输入： n = 2, edges = [[0,1,3]], k = 2
输出： 3
解释：
- 最初，图中有一个连通分量
{0, 1}。 - 在
time = 1或2时，图保持不变。 - 在
time = 3时，边[0, 1]被移除，图中形成k = 2个连通分量：{0}和{1}。因此，答案是 3。
示例 2：
输入： n = 3, edges = [[0,1,2],[1,2,4]], k = 3
输出： 4
解释：
- 最初，图中有一个连通分量
{0, 1, 2}。 - 在
time = 2时，边[0, 1]被移除，图中形成两个连通分量：{0}和{1, 2}。 - 在
time = 4时，边[1, 2]被移除，图中形成k = 3个连通分量：{0}、{1}和{2}。因此，答案是 4。
示例 3：
输入： n = 3, edges = [[0,2,5]], k = 2
输出： 0
解释：
- 由于图中已经存在
k = 2个连通分量{1}和{0, 2}，无需移除任何边。因此，答案是 0。
提示：
1 <= n <= 1050 <= edges.length <= 105edges[i] = [ui, vi, timei]0 <= ui, vi < nui != vi1 <= timei <= 1091 <= k <= n- 不存在重复的边。
解题思路
方法一：并查集
我们可以将边按时间从小到大排序，然后从时间最大的边开始依次将边加入图中，同时使用并查集维护当前图的连通分量数量。当连通分量数量小于 时，说明当前时间即为所求的最小时间。
时间复杂度 ，空间复杂度 ，其中 是反阿克曼函数。
class UnionFind:
def __init__(self, n):
self.p = list(range(n))
self.size = [1] * n
def find(self, x):
if self.p[x] != x:
self.p[x] = self.find(self.p[x])
return self.p[x]
def union(self, a, b):
pa, pb = self.find(a), self.find(b)
if pa == pb:
return False
if self.size[pa] > self.size[pb]:
self.p[pb] = pa
self.size[pa] += self.size[pb]
else:
self.p[pa] = pb
self.size[pb] += self.size[pa]
return True
class Solution:
def minTime(self, n: int, edges: List[List[int]], k: int) -> int:
edges.sort(key=lambda x: x[2])
uf = UnionFind(n)
cnt = n
for u, v, t in edges[::-1]:
if uf.union(u, v):
cnt -= 1
if cnt < k:
return t
return 0
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
The candidate must demonstrate a clear understanding of binary search principles and how they apply to this problem.
- question_mark
The candidate should effectively use union-find to manage connected components during the binary search.
- question_mark
A solid solution will include reasoning on time complexity and justify the approach with optimal space utilization.
常见陷阱
外企场景- error
Candidates might attempt to use brute force methods instead of binary search, leading to inefficient solutions.
- error
Misunderstanding the problem constraints and removing edges prematurely may cause incorrect results.
- error
Failing to optimize union-find operations with path compression and union by rank could lead to slower performance.
进阶变体
外企场景- arrow_right_alt
What if the graph starts already with k connected components?
- arrow_right_alt
How can this approach be modified for directed graphs?
- arrow_right_alt
What happens if there are more edges with the same time value?