2025-12-19：包含 K 个连通分量需要的最小时间。用go语言，给定一个含有 n 个顶点（编号 0 到 n-1）的无向图，图中的每条边用三元组 edges[i] = [ui, vi, timei

2025-12-19：包含 K 个连通分量需要的最小时间。用go语言，给定一个含有 n 个顶点（编号 0 到 n-1）的无向图，图中的每条边用三元组 edges[i] = [ui, vi, timei] 表示，含义是该无向边连接 ui 和 vi，并且会在时刻 timei 被删掉。再给定一个整数 k。

初始时图可以是连通的也可以是不连通的。现在希望找到一个最早的时间 t，使得把所有 time <= t 的边都移除后，图被分成的连通子图数量至少达到 k。连通子图指的是任意两个顶点间有路径相通，且该子图与外部没有边相连。

返回满足上述条件的最小 t。

1 <= n <= 100000。

0 <= edges.length <= 100000。

edges[i] = [ui, vi, timei]。

0 <= ui, vi < n。

ui != vi。

1 <= timei <= 1000000000。

1 <= k <= n。

不存在重复的边。

输入： n = 2, edges = [[0,1,3]], k = 2。

输出： 3。

解释：

最初，图中有一个连通分量 {0, 1}。

在 time = 1 或 2 时，图保持不变。

在 time = 3 时，边 [0, 1] 被移除，图中形成 k = 2 个连通分量：{0} 和 {1}。因此，答案是 3。

题目来自力扣3608。

📝 详细步骤说明

1. 边按时间降序排序

首先对所有边按照time字段进行降序排序。这样做的目的是让我们能够从最晚被删除的边开始处理，逐步向图中添加边，相当于逆向模拟边的删除过程。

排序后，时间最大的边排在前面，时间最小的边排在后面。

2. 初始化并查集

创建一个包含n个顶点的并查集数据结构。初始状态下：

• 每个顶点都是一个独立的连通分量
• 连通分量数量cc为n

并查集包含两个主要操作：

• find(x): 查找顶点x所在集合的代表元，同时进行路径压缩优化
• merge(from, to): 合并两个顶点所在的集合

3. 逆向添加边处理

按排序后的顺序遍历每条边（从时间最大的边开始）：

处理每条边e = [ui, vi, timei]的步骤：

1. 检查顶点ui和vi当前是否属于同一连通分量
2. 如果不在同一分量，则合并这两个分量，连通分量数量减1
3. 合并后检查当前连通分量数量是否小于k
   • 如果是，说明上一条处理的边（也就是当前边的前一条边）的时间就是我们要找的t
   • 因为继续添加边会导致连通分量进一步减少，而我们需要的是连通分量至少为k的最小时间

4. 确定结果

当发现添加某条边后连通分量数量变得小于k时：

• 返回当前边的时间值作为结果
• 这是因为移除所有time <= 当前边时间的边后，连通分量数量刚好达到k

如果遍历完所有边后连通分量数量仍然大于等于k，则返回0，表示不需要移除任何边就能满足条件。

⚙️ 算法复杂度分析

🕒 时间复杂度：O(m α(m, n))

• 边排序：O(m log m)，其中m是边的数量
• 并查集操作：每个find和merge操作的时间复杂度接近常数，为O(α(n))，其中α是反阿克曼函数
• 总体：排序占主导地位，但并查集操作也非常高效

💾 空间复杂度：O(n + m)

• 并查集存储：O(n)，用于存储每个顶点的父节点信息
• 边排序：O(m)，用于存储排序后的边列表
• 总体：线性空间复杂度，适合处理大规模数据

💡 核心思路总结

这个算法的关键在于逆向思考：不是正向模拟边的移除，而是从完全断开的状态开始逐步连接顶点。通过并查集高效维护连通分量，结合排序确保按时间顺序处理，最终在连通分量数量降至k以下时确定临界时间点。

Go完整代码如下：

packagemainimport("fmt""slices")typeunionFindstruct{fa[]int// 代表元ccint// 连通块个数}funcnewUnionFind(nint)unionFind{fa:=make([]int,n)// 一开始有 n 个集合 {0}, {1}, ..., {n-1}// 集合 i 的代表元是自己fori:=rangefa{fa[i]=i}returnunionFind{fa,n}}// 返回 x 所在集合的代表元// 同时做路径压缩，也就是把 x 所在集合中的所有元素的 fa 都改成代表元func(u unionFind)find(xint)int{// 如果 fa[x] == x，则表示 x 是代表元ifu.fa[x]!=x{u.fa[x]=u.find(u.fa[x])// fa 改成代表元}returnu.fa[x]}// 把 from 所在集合合并到 to 所在集合中func(u*unionFind)merge(from,toint){x,y:=u.find(from),u.find(to)ifx==y{// from 和 to 在同一个集合，不做合并return}u.fa[x]=y// 合并集合。修改后就可以认为 from 和 to 在同一个集合了u.cc--// 成功合并，连通块个数减一}funcminTime(nint,edges[][]int,kint)int{slices.SortFunc(edges,func(a,b[]int)int{returnb[2]-a[2]})u:=newUnionFind(n)for_,e:=rangeedges{u.merge(e[0],e[1])ifu.cc<k{// 这条边不能留，即移除所有 time <= e[2] 的边returne[2]}}return0// 无需移除任何边}funcmain(){n:=2edges:=[][]int{{0,1,3}}k:=2result:=minTime(n,edges,k)fmt.Println(result)}

Python完整代码如下：

# -*-coding:utf-8-*-fromtypingimportListclassUnionFind:def__init__(self,n:int):self.fa=list(range(n))# 代表元self.cc=n# 连通块个数deffind(self,x:int)->int:"""返回 x 所在集合的代表元，同时做路径压缩"""ifself.fa[x]!=x:self.fa[x]=self.find(self.fa[x])# fa 改成代表元returnself.fa[x]defmerge(self,from_:int,to:int)->None:"""把 from_ 所在集合合并到 to 所在集合中"""x,y=self.find(from_),self.find(to)ifx==y:# from_ 和 to 在同一个集合，不做合并returnself.fa[x]=y# 合并集合self.cc-=1# 成功合并，连通块个数减一defminTime(n:int,edges:List[List[int]],k:int)->int:# 按 time 从大到小排序edges.sort(key=lambdax:x[2],reverse=True)u=UnionFind(n)foru_,v,timeinedges:u.merge(u_,v)ifu.cc<k:# 这条边不能留，即移除所有 time <= time 的边returntimereturn0# 无需移除任何边if__name__=="__main__":n=2edges=[[0,1,3]]k=2result=minTime(n,edges,k)print(result)

C++完整代码如下：

#include<iostream>#include<vector>#include<algorithm>usingnamespacestd;classUnionFind{private:vector<int>fa;// 代表元intcc;// 连通块个数public:UnionFind(intn):fa(n),cc(n){// 一开始有 n 个集合 {0}, {1}, ..., {n-1}// 集合 i 的代表元是自己for(inti=0;i<n;i++){fa[i]=i;}}// 返回 x 所在集合的代表元// 同时做路径压缩，也就是把 x 所在集合中的所有元素的 fa 都改成代表元intfind(intx){// 如果 fa[x] == x，则表示 x 是代表元if(fa[x]!=x){fa[x]=find(fa[x]);// fa 改成代表元}returnfa[x];}// 把 from 所在集合合并到 to 所在集合中voidmerge(intfrom,intto){intx=find(from);inty=find(to);if(x==y){// from 和 to 在同一个集合，不做合并return;}fa[x]=y;// 合并集合。修改后就可以认为 from 和 to 在同一个集合了cc--;// 成功合并，连通块个数减一}intgetCC()const{returncc;}};intminTime(intn,vector<vector<int>>&edges,intk){// 按 time 从大到小排序sort(edges.begin(),edges.end(),[](constvector<int>&a,constvector<int>&b){returna[2]>b[2];});UnionFindu(n);for(constauto&e:edges){u.merge(e[0],e[1]);if(u.getCC()<k){// 这条边不能留，即移除所有 time <= e[2] 的边returne[2];}}return0;// 无需移除任何边}intmain(){intn=2;vector<vector<int>>edges={{0,1,3}};intk=2;intresult=minTime(n,edges,k);cout<<result<<endl;return0;}