并查集详解：从原理到实战，掌握动态连通性

1. 并查集到底在解决什么问题

第一次接触并查集，很多人会被这个名字吓到。“并”是合并，“查”是查询，“集”是集合，三个字拆开看其实已经把它的全部功能说完了：把两个集合合并成一个，查询某个元素属于哪个集合。就这么简单。

但就是这么简单的三个操作，在算法面试和实际工程里的出场率高得离谱。我做过一个粗略统计，在近几年的笔试真题里，并查集相关的题目出现频率稳定在前十。为什么？因为它解决了一类非常本质的问题：动态连通性。

什么叫动态连通性？你可以想象一个社交网络，用户之间不断加好友，你需要随时回答“用户A和用户B是否在同一个朋友圈里”。注意，这个“朋友圈”不是直接好友关系，而是通过一连串好友关系间接连通的。A认识B，B认识C，那A和C就在同一个圈子里。随着加好友的操作不断发生，圈子会不断合并，你需要动态地、快速地给出答案。

用图论的话说，就是在一个不断加边的无向图中，判断任意两个点是否连通。你当然可以用BFS或DFS每次重新搜一遍，但每次查询的代价是O(V+E)，如果有大量查询，性能会崩掉。并查集就是专门为这种场景设计的，它能让合并和查询的均摊时间复杂度降到几乎常数级别——具体来说是O(α(n))，其中α是阿克曼函数的反函数，对于任何你能想象到的n，α(n)都不会超过5。换句话说，你可以认为它就是O(1)。

我第一次真正理解并查集的价值，是在做一个图像处理的小项目时。当时需要把相邻的相似像素合并成区域，用BFS每次重新遍历效率太低，换成并查集之后，整个处理速度提升了一个数量级。从那以后，我就养成了一个习惯：只要看到“连通”“分组”“合并”“是否属于同一类”这些关键词，第一反应就是并查集。

这篇文章我会从最基础的结构讲起，把路径压缩和按秩合并这两个核心优化讲透，然后给出一个可以直接套用的模板，最后用几道经典例题带你走一遍完整的解题思路。不管你是刚学数据结构的新手，还是想复习一下准备面试的老手，应该都能从中找到有用的东西。

2. 并查集的核心原理与设计思路

2.1 用“帮派”来理解并查集

并查集最经典的比喻是帮派。每个帮派有一个老大，帮派里的每个成员都直接或间接地指向老大。如果两个帮派要合并，就让其中一个帮派的老大认另一个帮派的老大做老大。查询两个人是否在同一个帮派，就看他们俩的最终老大是不是同一个人。

这个比喻对应到数据结构上，就是一棵树。每个节点有一个父指针，根节点的父指针指向自己。查找操作就是从当前节点出发，沿着父指针一路向上，直到找到根节点。合并操作就是把一棵树的根节点挂到另一棵树的根节点下面。

先看最朴素的实现：

class UnionFind: def __init__(self, n): self.parent = list(range(n)) # 每个元素的父节点初始化为自己 def find(self, x): while self.parent[x] != x: x = self.parent[x] return x def union(self, x, y): root_x = self.find(x) root_y = self.find(y) if root_x != root_y: self.parent[root_x] = root_y

这个版本能跑，但有一个致命问题：如果合并的顺序不巧，树会退化成一条链。比如依次执行union(0,1)、union(1,2)、union(2,3)……最后find(0)需要走n步，复杂度退化成O(n)。这就失去了并查集的意义。

所以必须引入优化。并查集有两个经典优化：路径压缩和按秩合并。这两个优化各自都能把复杂度降下来，合在一起用效果最好。

2.2 路径压缩：一次查找，顺便把路修平

路径压缩的思路非常直观：既然我这次查找已经辛辛苦苦走到了根节点，那不如顺手把沿途所有节点的父指针都直接指向根节点。这样下次再查这些节点，一步就能到位。

还是用帮派的比喻：你去找老大汇报工作，路上经过了组长、队长、堂主。汇报完之后，老大说“以后你们几个直接来找我，不用层层上报了”。于是组长、队长、堂主的直属上级都变成了老大。下次你再找老大，一步到位。

路径压缩的递归实现：

def find(self, x): if self.parent[x] != x: self.parent[x] = self.find(self.parent[x]) return self.parent[x]

递归写法很简洁，但如果树很深，递归可能导致栈溢出。实际工程中我更推荐迭代写法：

def find(self, x): root = x while self.parent[root] != root: root = self.parent[root] # 路径压缩 while self.parent[x] != root: next_node = self.parent[x] self.parent[x] = root x = next_node return root

迭代版本分两步：先找到根节点，再把沿途所有节点直接挂到根节点上。虽然代码多几行，但避免了递归深度的问题，在数据量大的时候更稳妥。

注意：路径压缩会改变树的结构，但不会改变集合的划分。也就是说，压缩前后哪些元素属于同一个集合是不变的，只是树的形态变了。这一点在理解并查集时很关键。

2.3 按秩合并：让矮树挂到高树下

路径压缩解决的是“查找”的效率问题，而按秩合并解决的是“合并”的策略问题。如果每次合并都随便挂，可能会把一棵很高的树挂到一棵很矮的树下面，导致新树的高度增加，后续查找变慢。

按秩合并的原则是：总是把矮的树挂到高的树下面。这里的“秩”可以理解为树的高度（或者节点数量的近似）。如果两棵树高度不同，矮的挂到高的下面，新树的高度不变；如果高度相同，随便挂一个，新树高度加一。

class UnionFind: def __init__(self, n): self.parent = list(range(n)) self.rank = [0] * n # 秩初始为0 def find(self, x): if self.parent[x] != x: self.parent[x] = self.find(self.parent[x]) return self.parent[x] def union(self, x, y): root_x = self.find(x) root_y = self.find(y) if root_x == root_y: return # 按秩合并：矮树挂到高树下 if self.rank[root_x] < self.rank[root_y]: self.parent[root_x] = root_y elif self.rank[root_x] > self.rank[root_y]: self.parent[root_y] = root_x else: self.parent[root_y] = root_x self.rank[root_x] += 1

这里有一个常见的误区：很多人以为用了路径压缩之后，rank就不再准确反映树的高度了。确实，路径压缩会改变树的高度，但rank并不需要精确等于当前高度，它只是一个合并时的参考依据。即使rank不准确，按秩合并仍然能保证树的高度在O(log n)级别。所以两者可以安全地一起使用。

2.4 两种优化到底该不该同时用

理论上，路径压缩和按秩合并一起用，复杂度是O(α(n))，这是理论最优。但在实际刷题和工程中，我个人的经验是：只用路径压缩通常就够了。

原因很简单。路径压缩的均摊复杂度已经是O(α(n))级别（单独使用时是O(log n)均摊，但实际运行中非常接近常数），而按秩合并需要额外维护一个rank数组，增加了代码复杂度和内存开销。在绝大多数题目中，数据规模不会大到需要两者同时优化的程度。

不过有一种情况例外：如果你需要可持久化并查集，也就是保留历史版本，那就不能用路径压缩（因为路径压缩会修改历史结构），只能用按秩合并。这是另一个话题，这里不展开。

我的建议是：日常刷题和面试，写路径压缩就够了，代码简洁不容易出错。如果题目数据量特别大，或者你对性能有极致要求，再加上按秩合并。

3. 并查集的完整实现与实操要点

3.1 一份可以直接抄的模板

下面这份模板是我用了很多年的版本，兼顾了简洁性和性能。你可以直接复制到你的代码里用。

class UnionFind: def __init__(self, n): """初始化n个元素的并查集，编号0到n-1""" self.parent = list(range(n)) self.rank = [0] * n self.count = n # 连通分量个数 def find(self, x): """查找x的根节点，带路径压缩（迭代版）""" root = x while self.parent[root] != root: root = self.parent[root] # 路径压缩 while self.parent[x] != root: self.parent[x], x = root, self.parent[x] return root def union(self, x, y): """合并x和y所在的集合，返回是否发生了合并""" root_x = self.find(x) root_y = self.find(y) if root_x == root_y: return False # 按秩合并 if self.rank[root_x] < self.rank[root_y]: root_x, root_y = root_y, root_x self.parent[root_y] = root_x if self.rank[root_x] == self.rank[root_y]: self.rank[root_x] += 1 self.count -= 1 return True def connected(self, x, y): """判断x和y是否连通""" return self.find(x) == self.find(y) def get_count(self): """返回当前连通分量个数""" return self.count

这份模板有几个设计细节值得说明：

• count变量维护连通分量个数，很多题目需要这个信息，省得每次重新统计。
• union返回布尔值，表示是否真的发生了合并。如果两个元素本来就在同一个集合，返回False。这个返回值在某些题目里很有用，比如判断加边是否形成环。
• find用迭代写法，避免递归深度问题。
• 路径压缩的写法用了Python的元组赋值，一行搞定，但可读性稍差。如果你觉得不好理解，可以拆成三行。

3.2 初始化时的常见坑

初始化看起来简单，但有几个坑我踩过。

第一个坑是编号从0还是从1开始。有些题目元素编号从1开始，如果你直接开n大小的数组，访问n就会越界。解决办法是要么开n+1大小，要么在传入前统一减一。我个人的习惯是统一转成0-based，在读取输入的时候减一，这样内部逻辑不用特殊处理。

第二个坑是元素不是连续整数。比如元素是字符串或者大整数，不能直接作为数组下标。这时候需要用哈希表做映射，把每个元素映射到一个连续的整数编号。或者直接用字典实现并查集：

class UnionFindDict: def __init__(self): self.parent = {} def find(self, x): if x not in self.parent: self.parent[x] = x return x # 路径压缩 root = x while self.parent[root] != root: root = self.parent[root] while self.parent[x] != root: self.parent[x], x = root, self.parent[x] return root def union(self, x, y): root_x = self.find(x) root_y = self.find(y) if root_x != root_y: self.parent[root_x] = root_y

字典版本的好处是不需要预先知道元素范围，动态添加即可。缺点是常数比数组版本大，而且没有按秩合并。对于元素种类不确定的题目，字典版本很实用。

第三个坑是多组测试数据的重置。如果题目有多组测试用例，每次都要重新初始化并查集。千万不要忘了重置，否则上一组的数据会污染下一组。我一般把并查集封装成类，每组数据new一个对象，这样最不容易出错。

3.3 路径压缩的两种写法对比

路径压缩有递归和迭代两种写法，我前面都给了。这里再详细对比一下。

递归写法代码短，逻辑清晰，但有两个问题：一是递归深度受限于树的高度，虽然路径压缩后树很矮，但在压缩之前如果树退化成链，递归可能爆栈；二是函数调用有开销，在Python这种语言里递归性能不如迭代。

迭代写法代码长一些，但没有栈溢出风险，性能也更好。我实测过，在10万次操作的规模下，迭代版本比递归版本快大约20%到30%。所以如果你追求性能，用迭代版本。

不过有一种情况递归写法更方便：带权并查集。带权并查集需要在查找过程中累加路径上的权值，递归写法处理起来更自然。这个后面会讲到。

3.4 并查集的复杂度到底怎么算

很多人只知道并查集“很快”，但说不清楚到底多快。这里我尽量用通俗的方式解释一下。

只用路径压缩不用按秩合并时，单次操作的均摊复杂度是O(log n)。注意是均摊，不是每次都是O(log n)。有些操作可能很快，有些稍慢，但平均下来是O(log n)。

同时用路径压缩和按秩合并时，单次操作的均摊复杂度是O(α(n))。α是阿克曼函数的反函数，增长极其缓慢。对于n等于宇宙中原子总数（约10^80）的情况，α(n)也不超过4。所以你可以认为它是常数。

实际测试中，对于100万个元素、100万次操作，并查集的总耗时通常在几百毫秒级别。这个性能对于绝大多数应用场景都绰绰有余。

实操心得：如果你在面试中被问到并查集的复杂度，回答O(α(n))并解释α的含义，基本就能让面试官满意。如果能进一步说明“实际可视为O(1)”，效果更好。

4. 经典例题实战拆解

4.1 朋友圈问题：并查集最直接的应用

这是并查集最经典的入门题。题目描述是：有n个人，编号1到n。给出m对好友关系，好友关系具有传递性。问有多少个朋友圈。

这道题就是并查集的直译。每个人初始是一个独立的集合，每读入一对好友关系就合并两个集合，最后统计有多少个不同的根节点。

def find_circle_num(n, relationships): uf = UnionFind(n) for a, b in relationships: uf.union(a - 1, b - 1) # 转成0-based return uf.get_count()

这道题的关键点在于理解“好友关系具有传递性”这句话。A和B是好友，B和C是好友，那么A和C也在同一个朋友圈。这正是并查集合并操作要解决的问题。

我见过一些初学者试图用BFS来做这道题，每次从一个未访问的人出发做一次BFS，统计连通分量个数。这样做当然也对，但代码量大得多，而且每次都要重新遍历图。并查集只需要一遍扫描加合并，代码简洁，效率也高。

这道题还有一个变体：如果好友关系是动态增加的，每次增加后都要查询朋友圈数量。用BFS的话每次都要重新算，而并查集只需要在合并时更新count变量，查询是O(1)的。这就是并查集在动态场景下的优势。

4.2 冗余连接：用并查集检测环

这道题是这样的：给出一棵树的n条边（实际上是一棵树多了一条边，形成了环），要求找出那条多余的边，使得删掉它之后图变成一棵树。如果有多个答案，返回最后出现的那条。

思路很直接：遍历每条边，如果两个端点已经连通，说明这条边就是多余的（它形成了一个环）；如果还没连通，就合并它们。

def find_redundant_connection(edges): n = len(edges) uf = UnionFind(n + 1) # 节点编号1到n for u, v in edges: if uf.connected(u, v): return [u, v] uf.union(u, v) return []

这道题的精髓在于：在一棵树中，任意两个节点之间恰好有一条路径。如果加入一条边后两个节点已经连通，那这条边必然形成环。并查集的connected操作正好能O(1)判断连通性。

我第一次做这道题的时候，想的是用DFS检测环，每次加边后跑一遍DFS。后来发现并查集只需要一遍遍历，而且不需要建图。从那以后，凡是遇到“动态加边判断环”的题目，我都优先考虑并查集。

这道题还有一个进阶版本：如果图不是树加一条边，而是任意图，要求找出所有形成环的边。思路是一样的，只是不能提前返回，要把所有冗余边都收集起来。

4.3 岛屿数量：并查集的二维应用

这道题是LeetCode上的经典题目：给一个由'1'（陆地）和'0'（水）组成的二维网格，计算岛屿的数量。岛屿由水平或垂直方向上相邻的陆地连接而成。

常规做法是DFS或BFS，但并查集也能做，而且思路很清晰。把每个'1'看作一个元素，遍历网格，如果当前格子是'1'，检查它的右边和下边（避免重复），如果是'1'就合并。最后统计有多少个不同的根节点，就是岛屿数量。

def num_islands(grid): if not grid or not grid[0]: return 0 rows, cols = len(grid), len(grid[0]) uf = UnionFind(rows * cols) water_count = 0 for i in range(rows): for j in range(cols): if grid[i][j] == '0': water_count += 1 continue # 只检查右边和下边，避免重复 if i + 1 < rows and grid[i + 1][j] == '1': uf.union(i * cols + j, (i + 1) * cols + j) if j + 1 < cols and grid[i][j + 1] == '1': uf.union(i * cols + j, i * cols + j + 1) return uf.get_count() - water_count

这里有一个细节：水域格子也被初始化成了独立的集合，所以最后要用总集合数减去水域格子数。另一种做法是只对陆地格子建并查集，但需要额外的映射，代码更复杂。我倾向于前者，简单直接。

这道题用并查集做的时间复杂度和DFS一样，都是O(rows * cols * α)。但并查集的优势在于，如果网格是动态变化的（比如某些格子从水变成陆地），并查集可以增量更新，而DFS需要重新计算。这就是所谓的“动态连通性”问题。

4.4 等式方程的可满足性：并查集的逻辑推理

这道题很有意思：给出一组等式和不等式，判断是否存在一种变量赋值使得所有式子同时成立。比如["a==b", "b!=c", "a==c"]就是不可满足的，因为a==b且a==c推出b==c，与b!=c矛盾。

解题思路分两步：先把所有等式用并查集合并，然后检查所有不等式，如果不等式两边的变量在同一个集合里，就矛盾了。

def equations_possible(equations): uf = UnionFindDict() # 第一步：处理所有等式 for eq in equations: if eq[1] == '=': uf.union(eq[0], eq[3]) # 第二步：检查不等式 for eq in equations: if eq[1] == '!': if uf.find(eq[0]) == uf.find(eq[3]): return False return True

这道题的关键洞察是：等式具有传递性，可以用并查集维护等价类；不等式只需要检查两边是否在同一个等价类中。先处理等式再处理不等式的顺序很重要，因为等式合并后，不等式的检查才有意义。

这道题让我意识到，并查集不仅能处理图论问题，还能处理逻辑推理问题。凡是涉及“等价关系”的场景，并查集都是一个强有力的工具。等价关系有三个性质：自反性、对称性、传递性。并查集天然满足这三个性质。

4.5 带权并查集：处理有距离的关系

前面讲的都是普通的并查集，只能回答“是否连通”。但有些题目需要回答“连通的距离是多少”。比如经典的“食物链”问题：A吃B，B吃C，C吃A，给出若干关系，判断有多少句假话。

这类问题需要用带权并查集。每个节点除了父指针，还维护一个权值，表示它与父节点的某种关系。在查找过程中，权值会累加，最终得到它与根节点的关系。

带权并查集的find操作需要同时更新权值：

class WeightedUnionFind: def __init__(self, n): self.parent = list(range(n)) self.weight = [0] * n # weight[x]表示x到parent[x]的权值 def find(self, x): if self.parent[x] != x: root = self.find(self.parent[x]) self.weight[x] += self.weight[self.parent[x]] self.parent[x] = root return self.parent[x] def union(self, x, y, w): """合并x和y，要求weight[y] - weight[x] = w""" root_x = self.find(x) root_y = self.find(y) if root_x == root_y: return self.weight[x] - self.weight[y] == w self.parent[root_x] = root_y self.weight[root_x] = self.weight[y] + w - self.weight[x] return True

带权并查集的难点在于权值更新的公式推导。以“食物链”为例，权值0表示同类，1表示吃，2表示被吃。合并时的公式需要根据具体问题的语义来推导。

我建议初学者先掌握普通并查集，等遇到需要维护关系的题目时再学带权并查集。不要一上来就啃带权版本，容易劝退。

5. 常见问题与排查技巧实录

5.1 并查集问题速查表

5.2 我踩过的三个坑

第一个坑是在union之前忘记find。有一次我写代码，直接比较两个元素是否相等来判断是否合并，结果当然错了。并查集判断的是根节点是否相同，不是元素本身是否相同。这个错误很低级，但在赶时间的时候真的会犯。

第二个坑是路径压缩写错导致死循环。迭代版路径压缩的第二步，如果写错了指针更新的顺序，可能导致x在原地打转。我当时的错误写法是先把parent[x]改成root，然后x = parent[x]，结果x变成了root，循环条件永远不满足。正确的做法是先用临时变量保存next，再更新。

第三个坑是在需要判断环的题目中，先union再判断。正确的顺序是先判断connected，如果已经连通说明形成环，否则再union。顺序反了就会漏掉环。

避坑技巧：写完并查集代码后，用一个小例子手动模拟一遍。比如3个元素，合并1和2，再合并2和3，然后查询1和3是否连通。手动走一遍find和union的流程，能发现大部分逻辑错误。

5.3 什么时候不该用并查集

并查集虽然强大，但也不是万能的。以下几种情况不适合用并查集：

• 需要删除边：并查集只支持加边，不支持删边。如果题目需要动态删边，需要用更复杂的数据结构，比如动态树。
• 需要查询路径信息：并查集只维护连通性，不维护路径的具体信息。如果需要知道两点之间的最短路径，得用BFS或最短路算法。
• 需要方向性：并查集处理的是无向关系。如果关系有方向，比如A指向B，并查集就不适用了。
• 需要频繁查询集合内元素：并查集不维护集合内的元素列表，如果需要枚举集合内所有元素，需要额外维护。

理解这些限制，能帮你在合适的场景选择并查集，不合适的场景果断换方案。

5.4 面试中的并查集考察点

根据我的面试经验，并查集相关的面试题通常考察以下几个层面：

第一层是基本实现。面试官会让你手写一个并查集，考察你对parent数组、find、union的理解。这一层只要模板背熟就没问题。

第二层是优化原理。面试官会问路径压缩和按秩合并的原理，以及为什么能把复杂度降到O(α(n))。这一层需要理解摊还分析的基本思想。

第三层是问题建模。面试官给一个实际问题，你需要识别出它是连通性问题，然后转化为并查集。这一层最难，需要大量练习才能培养出直觉。

第四层是变体应用。比如带权并查集、可持久化并查集、二维并查集等。这一层属于加分项，不是每个面试都会问到。

我的建议是：前两层必须扎实，第三层多刷题培养感觉，第四层了解即可，遇到再深入。

5.5 刷题路线建议

如果你刚开始学并查集，我建议按以下顺序刷题：

1. 朋友圈/省份数量（入门，理解基本操作）
2. 冗余连接（理解环检测）
3. 岛屿数量（二维应用）
4. 等式方程的可满足性（逻辑推理）
5. 最长连续序列（并查集+哈希）
6. 食物链（带权并查集）

每道题做完后，不要只看答案，要自己手动模拟一遍并查集的变化过程。画图把每次find和union后的树结构画出来，这样能加深理解。

我当初学并查集的时候，把每道题的并查集变化过程都画在了纸上。画了十几道题之后，基本上看到题目就能条件反射地想到并查集。这个笨办法很有效，推荐你也试试。

6. 并查集的扩展与进阶方向

6.1 可持久化并查集

普通并查集只维护当前状态，如果题目需要查询历史某个时刻的连通性，就需要可持久化并查集。实现方式是用可持久化数组维护parent，并且不能用路径压缩（因为路径压缩会修改历史版本），只能用按秩合并。

可持久化并查集的复杂度是O(log^2 n)，比普通并查集慢，但能支持版本回溯。这类题目在竞赛中偶尔出现，面试中很少考。

6.2 并查集与其它数据结构的结合

并查集经常和别的数据结构结合使用。比如并查集+链表，可以在合并集合的同时维护集合内的元素顺序；并查集+堆，可以在合并集合的同时维护集合内的最值；并查集+字典树，可以处理字符串的连通性问题。

我做过一个项目，需要把相似的字符串分组。做法是用字典树找相似关系，然后用并查集合并。这种组合思路在工程中很常见。

6.3 并查集在工程中的应用

并查集不只是刷题用的，实际工程中也有很多应用。比如：

• 图像处理：连通区域标记，把相邻的相似像素合并成区域。
• 网络管理：判断两台主机是否在同一个子网中。
• 编译器优化：变量等价类分析，把等价的变量合并。
• 社交网络：好友推荐，找出可能认识的人。
• 游戏开发：地图连通性判断，比如判断两个区域是否可达。

我在一个图像处理项目中用并查集做连通区域标记，代码量比BFS少了三分之二，性能还更好。从那以后，凡是遇到连通性问题，我都会先考虑并查集。

6.4 并查集的性能调优经验

如果你在工程中使用并查集，有几个性能调优的点值得注意：

第一，用数组而不是字典。数组的随机访问是O(1)且常数很小，字典有哈希开销。如果元素编号连续，一定用数组。

第二，路径压缩用迭代不用递归。迭代版本没有函数调用开销，也没有栈溢出风险。

第三，按秩合并的rank可以用size代替。用集合大小作为合并依据，效果和rank差不多，而且size还能用于其它统计。

第四，批量操作时减少find调用。比如合并多个元素时，可以先找到所有根节点，再统一合并，减少重复find。

第五，预分配数组。如果知道元素数量上限，提前分配好数组，避免动态扩容。

这些优化在数据量大的时候效果明显。我实测过，在100万数据规模下，优化后的并查集比朴素版本快5倍以上。

6.5 一个完整的工程级并查集实现

最后给一个我在工程中使用的并查集实现，支持泛型元素、路径压缩、按秩合并、连通分量统计：

class UnionFind: def __init__(self, elements=None): self.parent = {} self.rank = {} self.count = 0 if elements: for e in elements: self.add(e) def add(self, x): if x not in self.parent: self.parent[x] = x self.rank[x] = 0 self.count += 1 def find(self, x): self.add(x) root = x while self.parent[root] != root: root = self.parent[root] while self.parent[x] != root: self.parent[x], x = root, self.parent[x] return root def union(self, x, y): root_x = self.find(x) root_y = self.find(y) if root_x == root_y: return False if self.rank[root_x] < self.rank[root_y]: root_x, root_y = root_y, root_x self.parent[root_y] = root_x if self.rank[root_x] == self.rank[root_y]: self.rank[root_x] += 1 self.count -= 1 return True def connected(self, x, y): return self.find(x) == self.find(y) def get_count(self): return self.count def get_groups(self): groups = {} for x in self.parent: root = self.find(x) groups.setdefault(root, []).append(x) return list(groups.values())

这个版本支持动态添加元素，适合元素种类不确定的场景。get_groups方法可以枚举所有连通分量，在某些题目中很有用。

我在实际项目中使用这个实现处理过百万级别的数据，性能完全够用。如果你有更极致的性能需求，可以把字典换成数组，但大多数场景下字典版本已经足够了。

并查集这个数据结构，入门容易，精通也不难，但真正用好需要大量的练习和实战。我建议你把这篇文章里的模板和例题都亲手敲一遍，然后找十几道相关题目刷一刷。刷完之后，你会发现自己对连通性问题的敏感度明显提升，很多以前觉得复杂的题目，现在一眼就能看出是并查集的变体。这种直觉，就是刷题和实战积累出来的。