什么是并查集
并查集是一种用于处理不相交集合的数据结构，主要支持两种操作：
- Union（合并）：将两个集合合并为一个集合
- Find（查找）：判断某个元素属于哪个集合
并查集特别适合解决连通性问题，例如判断两个元素是否在同一个集合中。
并查集的基本实现
核心数据结构
typeUnionFindstruct{parent[]int// parent[i] 表示元素 i 的父节点rank[]int// rank[i] 表示以 i 为根的树的高度（用于按秩合并）}三个核心操作
1. 初始化
每个元素初始时都是独立的集合，自己是自己的父节点。
funcNewUnionFind(nint)*UnionFind{parent:=make([]int,n)rank:=make([]int,n)fori:=0;i<n;i++{parent[i]=i// 初始时自己是自己的父节点rank[i]=1}return&UnionFind{parent:parent,rank:rank}}2. Find（查找）- 路径压缩优化
查找元素的根节点，同时进行路径压缩，将路径上的所有节点直接连到根节点。
func(uf*UnionFind)Find(xint)int{ifuf.parent[x]!=x{uf.parent[x]=uf.Find(uf.parent[x])// 路径压缩}returnuf.parent[x]}路径压缩的作用：将树的高度降低，后续操作更快。时间复杂度接近 O(1)。
3. Union（合并）- 按秩合并优化
将两个集合合并，优先将高度小的树合并到高度大的树下。
func(uf*UnionFind)Union(x,yint){rootX:=uf.Find(x)rootY:=uf.Find(y)ifrootX==rootY{return// 已经在同一集合}// 按秩合并：将高度小的树连到高度大的树下ifuf.rank[rootX]<uf.rank[rootY]{uf.parent[rootX]=rootY}elseifuf.rank[rootX]>uf.rank[rootY]{uf.parent[rootY]=rootX}else{uf.parent[rootY]=rootX uf.rank[rootX]++}}按秩合并的作用：避免树退化成链表，保持树的平衡。
辅助方法
// 判断两个元素是否连通func(uf*UnionFind)IsConnected(x,yint)bool{returnuf.Find(x)==uf.Find(y)}// 重置节点（某些场景需要）func(uf*UnionFind)Reset(xint){uf.parent[x]=x uf.rank[x]=1}并查集的应用场景
1. 判断连通性
- 网络连接
- 朋友圈问题
- 岛屿数量
2. 动态连通性
- 判断图中是否存在环
- 最小生成树（Kruskal 算法）
3. 分组/聚类
- 账户合并
- 社交网络分析
4. 带时间维度的连通性（本题）
- 需要按时间顺序处理
- 可能需要回退/重置操作
并查集常见套路
套路1：基础连通性判断
uf:=NewUnionFind(n)// 建立连接uf.Union(x,y)// 判断连通ifuf.IsConnected(a,b){// 处理逻辑}套路2：统计集合数量
通过统计有多少个根节点来确定集合数量。
count:=0fori:=0;i<n;i++{ifuf.Find(i)==i{count++}}套路3：带权并查集
维护节点间的关系（距离、差值等）。
套路4：时间维度处理
- 按时间排序
- 分时间段处理
- 需要时进行回退
复杂度分析
使用路径压缩和按秩合并优化后：
- 单次操作时间复杂度：O(α(n))，α 是阿克曼函数的反函数，增长极慢，实际可看作 O(1)
- 空间复杂度：O(n)
实战案例：LeetCode 2092. 找出知晓秘密的所有专家
题目描述
给定 n 个专家（编号 0 到 n-1），一个会议列表 meetings[i] = [xi, yi, timei]，以及初始知道秘密的 firstPerson。
- 专家 0 在时间 0 时知道秘密，并分享给 firstPerson
- 每次会议时，知道秘密的专家会分享给对方
- 同一时间的秘密传播是瞬时的
- 返回所有最终知道秘密的专家列表
解题分析
这是一道带时间维度的并查集问题，体现了"套路4"的应用。
核心难点
- 时间维度：需要按时间顺序处理会议
- 同时刻处理：同一时刻的会议必须一起处理（瞬时传播）
- 回退机制：如果某人没有连通到专家0，需要撤销其加入
解题步骤
- 初始化：将专家 0 和 firstPerson 合并到同一集合
- 按时间排序：将所有会议按时间升序排列
- 分时间段处理：
- 收集同一时刻的所有会议
- 对这些会议进行 Union 操作
- 检查参会者是否与专家 0 连通
- 关键：不连通的参会者需要 Reset（回退）
- 收集结果：统计所有与专家 0 连通的专家
代码实现
funcfindAllPeople(nint,meetings[][]int,firstPersonint)[]int{uf:=NewUnionFind(n)uf.Union(0,firstPerson)// 按时间排序sort.Slice(meetings,func(i,jint)bool{returnmeetings[i][2]<meetings[j][2]})// 按时间分组处理i:=0fori<len(meetings){currentTime:=meetings[i][2]peopleInMeetings:=make(map[int]bool)// 处理同一时间的所有会议j:=iforj<len(meetings)&&meetings[j][2]==currentTime{x,y:=meetings[j][0],meetings[j][1]uf.Union(x,y)peopleInMeetings[x]=truepeopleInMeetings[y]=truej++}// 回退：不连通的参会者需要重置forperson:=rangepeopleInMeetings{if!uf.IsConnected(person,0){uf.Reset(person)}}i=j}// 收集结果result:=make([]int,0)fori:=0;i<n;i++{ifuf.IsConnected(i,0){result=append(result,i)}}returnresult}复杂度分析
- 时间复杂度：O(m log m + m α(n))
- 排序：O(m log m)
- 并查集操作：O(m α(n)) ≈ O(m)
- 空间复杂度：O(n)
关键技巧总结
- 时间分组：同一时间的操作必须批量处理
- 回退机制：使用 Reset 撤销不合法的合并
- 连通性判断：只保留与"源点"连通的节点
总结
并查集是处理动态连通性问题的利器，掌握以下要点：
✅基本操作：Find（路径压缩） + Union（按秩合并）
✅常见套路：连通性判断、集合统计、时间维度处理
✅优化技巧：路径压缩 + 按秩合并，时间复杂度接近 O(1)
✅灵活应用：根据题目需求添加 Reset、权重等扩展功能
通过这道题目，我们学会了如何处理带时间维度的并查集问题，这是并查集高级应用的典型场景。
