并查集题解合并之前先问清楚关系会不会传递并查集适合解决“连通性”和“等价关系”问题。很多题一看到合并就想用并查集但并不是所有关系都能合并。使用前先问这个关系是否传递如果 A 和 B 同组B 和 C 同组是否能推出 A 和 C 同组并查集不是万能胶水。关系能传递才适合粘。一、并查集的核心操作并查集只有两个核心操作find 找代表union 合并集合。flowchart TD A[元素 x] -- B[find(x)] C[元素 y] -- D[find(y)] B -- E{代表是否相同} D -- E E --|否| F[union 合并] E --|是| G[已经连通]路径压缩和按秩合并让它非常快近似 O(1)。二、代码模板class DSU: def __init__(self, n): self.parent list(range(n)) self.rank [0] * n def find(self, x): if self.parent[x] ! x: self.parent[x] self.find(self.parent[x]) return self.parent[x] def union(self, a, b): ra, rb self.find(a), self.find(b) if ra rb: return False if self.rank[ra] self.rank[rb]: ra, rb rb, ra self.parent[rb] ra if self.rank[ra] self.rank[rb]: self.rank[ra] 1 return Trueunion返回是否真的合并很多题用它判断是否形成环。三、适用题型朋友圈、省份数量、冗余连接、岛屿数量、等式方程可满足性都很适合并查集。它们共同点是关系能传递。不适合的场景有方向依赖、最短路径、顺序约束。比如“谁先完成谁”这不是并查集合并能解决的。四、复杂度和边界初始化 O(n)每次 find/union 近似 O(1)。边界要注意编号从 0 还是 1 开始二维网格映射到一维时不要算错。idx r * cols c映射错了并查集会把毫不相干的格子合在一起结果很有喜剧效果但提交会很悲剧。并查集还常用于“等式和不等式”判断。先合并所有相等关系再检查不等关系是否冲突。顺序很重要不能边看边随便判断。def equationsPossible(equations): dsu DSU(26) for e in equations: if e[1:3] : dsu.union(ord(e[0])-97, ord(e[3])-97) for e in equations: if e[1:3] ! and dsu.find(ord(e[0])-97) dsu.find(ord(e[3])-97): return False return True这个例子能说明并查集的典型流程先建立等价类再验证约束。它不是用来求路径而是用来维护集合关系。五、总结并查集适合传递关系和连通性问题。核心是 find、union、路径压缩和按秩合并。合并之前先问清楚关系会不会传递。能传递放心粘不能传递换工具。
