当前位置：首页 > news >正文

并查集题解：合并之前，先问清楚关系会不会传递

news 2026/7/3 22:36:45

并查集题解：合并之前，先问清楚关系会不会传递

并查集适合解决“连通性”和“等价关系”问题。很多题一看到合并就想用并查集，但并不是所有关系都能合并。使用前先问：这个关系是否传递？如果 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 True

union返回是否真的合并，很多题用它判断是否形成环。

三、适用题型

朋友圈、省份数量、冗余连接、岛屿数量、等式方程可满足性，都很适合并查集。它们共同点是关系能传递。

不适合的场景：有方向依赖、最短路径、顺序约束。比如“谁先完成谁”，这不是并查集合并能解决的。

四、复杂度和边界

初始化 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

这个例子能说明并查集的典型流程：先建立等价类，再验证约束。它不是用来求路径，而是用来维护集合关系。