1. 并查集基础从连通性问题到高效解决方案在计算机科学中处理元素分组和连通性问题是许多算法的基础需求。想象你正在管理一个大型社交网络需要快速判断两个人是否属于同一个朋友圈或者需要将两个原本独立的圈子合并——这正是并查集(Disjoint Set Union, DSU)的用武之地。并查集是一种树型数据结构用于处理不相交集合的合并与查询问题。它的核心操作可以用三个函数来描述make_set(x)创建一个只包含元素x的新集合find(x)找到x所属集合的代表元素也称为根union(x, y)合并包含x和y的两个集合基础实现中我们通常使用数组来存储每个元素的父节点指针。初始时每个元素都是自己的父节点即自己是自己的代表。find操作通过不断追溯父节点直到找到根节点而union操作则将两个集合的根节点连接起来。class DSU: 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): x_root self.find(x) y_root self.find(y) if x_root ! y_root: self.parent[y_root] x_root这种朴素实现的最坏时间复杂度是O(n)的因为树可能会退化成链表。但通过两种优化技术——路径压缩和按秩合并——我们可以达到近乎常数时间的效率。路径压缩在find操作中实现当我们查找某个元素的根时顺便将该元素直接指向根扁平化树结构def find(self, x): if self.parent[x] ! x: self.parent[x] self.find(self.parent[x]) # 路径压缩 return self.parent[x]按秩合并则在union操作中保持树的平衡总是将较小的树合并到较大的树下def __init__(self, n): self.parent list(range(n)) self.rank [0] * n # 初始秩为0 def union(self, x, y): x_root self.find(x) y_root self.find(y) if x_root y_root: return # 按秩合并 if self.rank[x_root] self.rank[y_root]: self.parent[x_root] y_root else: self.parent[y_root] x_root if self.rank[x_root] self.rank[y_root]: self.rank[x_root] 1这两种优化技术共同作用使得并查集的每个操作平均时间复杂度降低到O(α(n))其中α是阿克曼函数的反函数对于任何实际应用中可能遇到的n值α(n)都不会超过5因此可以认为是近乎常数时间。提示在实际编码面试中路径压缩单独使用已经足够高效且实现更简单。按秩合并虽然理论上更优但代码复杂度增加除非特别要求通常路径压缩就是够用的选择。并查集的应用场景非常广泛从图的连通分量检测如Kruskal最小生成树算法、图像处理中的区域标记到社交网络中的好友关系管理。它的高效性尤其适合处理动态连通性问题——即集合结构会随着操作不断变化的场景。2. 带权并查集维护元素间的相对关系标准并查集只能告诉我们元素是否属于同一集合但很多时候我们需要知道集合内元素之间的具体关系。这就是带权并查集(Weighted DSU)的用武之地——它在保持高效的同时还能维护元素间的相对关系。带权并查集的核心思想是为每个节点到其父节点的边赋予一个权值这个权值表示两个元素之间的关系。在find操作进行路径压缩时我们需要同时维护这些权值的正确性在union操作合并集合时需要根据具体问题确定如何合并权值。以经典的食物链问题为例POJ 1182动物之间存在A吃B、B吃C、C吃A的循环关系。我们需要判断给定的关系是否与之前的信息矛盾。这时可以用带权并查集其中权值表示当前节点与父节点的关系0同类1吃父节点2被父节点吃。class WeightedDSU: def __init__(self, n): self.parent list(range(n)) self.relation [0] * n # 0: 同类, 1: 吃父节点, 2: 被父节点吃 def find(self, x): if self.parent[x] ! x: orig_parent self.parent[x] self.parent[x] self.find(self.parent[x]) # 路径压缩 # 更新关系当前节点与根的关系 (当前与原父关系 原父与根关系) % 3 self.relation[x] (self.relation[x] self.relation[orig_parent]) % 3 return self.parent[x] def union(self, x, y, rel): rel: x与y的关系 (0: 同类, 1: x吃y, 2: x被y吃) x_root self.find(x) y_root self.find(y) if x_root y_root: return False # 无需合并 # 将y_root合并到x_root下 self.parent[y_root] x_root # 更新关系通过向量计算确定新的关系 # x-x_root: relation[x], y-y_root: relation[y], x与y: rel # 需要找到y_root-x_root的关系 self.relation[y_root] (self.relation[x] - rel - self.relation[y]) % 3 return True另一个典型应用是解决等式方程问题如LeetCode 990。给定一组形如ab或a!b的方程判断它们是否矛盾。我们可以用带权并查集其中权值表示两个变量的差值class EquationDSU: def __init__(self): self.parent {} self.weight {} # parent[x] y时weight[x]表示x - y的值 def find(self, x): if x not in self.parent: self.parent[x] x self.weight[x] 0.0 return x if self.parent[x] ! x: orig_parent self.parent[x] self.parent[x] self.find(self.parent[x]) self.weight[x] self.weight[orig_parent] return self.parent[x] def union(self, x, y, value): value表示x - y的值 x_root self.find(x) y_root self.find(y) if x_root y_root: return abs(self.weight[x] - self.weight[y] - value) 1e-5 # 合并两个集合 self.parent[x_root] y_root self.weight[x_root] self.weight[y] value - self.weight[x] return True带权并查集的关键在于定义清晰的权值含义差、比值、特定关系等在路径压缩时正确维护权值的传递性在合并集合时正确处理权值的组合关系注意权值的更新公式通常需要根据具体问题推导。一个实用技巧是画向量图——将每个关系看作向量通过向量加减来确定合并后的新关系。3. 扩展域并查集用空间换逻辑清晰度当带权并查集的权值关系变得复杂时另一种解决方案是扩展域并查集(Extended Domain DSU)也称为种类并查集。它的核心思想是将每个元素拆分为多个逻辑节点通过在不同域中的连接关系来表达复杂的约束条件。扩展域并查集特别适合处理敌人的敌人是朋友这类逻辑关系。以经典的团伙问题为例已知一些人是朋友相互认识一些人是敌人相互不认识且朋友的朋友是朋友敌人的敌人也是朋友。判断最多可能有多少个独立的团伙。在这种情况下我们可以将每个人的信息拆分为两个域域A表示朋友关系域B表示敌人关系具体实现时对于元素x我们用x表示其朋友域xn表示其敌人域n是总元素数。当x和y是朋友时我们合并x和y同时合并xn和yn当x和y是敌人时我们合并x和yn同时合并y和xn。class ExtendedDSU: def __init__(self, n): self.parent list(range(2 * n)) # 前n个是朋友域后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, x, y, is_friend): if is_friend: # 朋友关系合并x和y以及xn和yn self.parent[self.find(x)] self.find(y) self.parent[self.find(x n)] self.find(y n) else: # 敌人关系合并x和yn以及y和xn self.parent[self.find(x)] self.find(y n) self.parent[self.find(y)] self.find(x n) def is_conflict(self, x, y, is_friend): if is_friend: # 检查x和yn是否在同一集合即x和y是否是敌人 return self.find(x) self.find(y n) else: # 检查x和y是否在同一集合即x和y是否是朋友 return self.find(x) self.find(y)扩展域并查集相比带权并查集的优点是逻辑更加清晰直观特别是在关系类型较多的情况下。例如处理三种关系朋友、敌人、中立时可以扩展为三个域class ThreeRelationDSU: def __init__(self, n): self.parent list(range(3 * n)) # 0~n-1:朋友域, n~2n-1:敌人域, 2n~3n-1:中立域 def set_relation(self, x, y, relation): relation: 0-朋友, 1-敌人, 2-中立 if relation 0: self.union(x, y) self.union(x n, y n) self.union(x 2 * n, y 2 * n) elif relation 1: self.union(x, y n) self.union(x n, y 2 * n) self.union(x 2 * n, y) else: self.union(x, y 2 * n) self.union(x n, y) self.union(x 2 * n, y n)扩展域并查集的空间复杂度是O(kn)其中k是关系类型数。虽然比带权并查集的O(n)要高但在处理复杂关系时代码的可读性和可维护性往往更好。选择哪种实现取决于具体问题和个人偏好。实战技巧当关系类型超过3种时带权并查集通常更合适。而对于二值关系是/否朋友/敌人等扩展域实现往往更简单不易出错。4. 并查集的高级应用与性能优化并查集在实际工程中的应用远比基础算法题目丰富。让我们探讨几个高级应用场景和相应的优化技巧。4.1 动态图的连通性维护在需要实时维护图连通性的场景中如网络拓扑管理传统的DFS/BFS方法在每次边增删后都需要重新计算效率低下。使用并查集可以高效处理边的添加但标准实现无法处理删除操作。可删点并查集通过引入虚节点技术解决这一问题class DeletableDSU: def __init__(self, n): self.parent list(range(2 * n)) # 前n个是实际节点后n个是虚节点 self.real list(range(n)) # 实际节点到虚节点的映射 self.next_virtual n # 下一个可用的虚节点 def find(self, x): x self.real[x] if self.parent[x] ! x: self.parent[x] self.find(self.parent[x]) return self.parent[x] def union(self, x, y): x_root self.find(x) y_root self.find(y) if x_root ! y_root: self.parent[y_root] x_root def delete(self, x): 删除节点x为其分配一个新的虚节点 self.real[x] self.next_virtual self.parent[self.next_virtual] self.next_virtual self.next_virtual 1这种技术通过为每个删除操作创建新的虚节点来保持原有连接关系代价是空间复杂度增加。对于频繁删除的场景可以考虑更复杂的基于时间戳的区间并查集。4.2 二维网格问题的并查集优化在处理二维网格如图像处理、游戏地图时常规的并查集需要对每个网格点进行线性编号。更高效的做法是利用网格的局部性实现基于块的路径压缩class GridDSU: def __init__(self, rows, cols): self.rows rows self.cols cols self.parent [(r, c) for r in range(rows) for c in range(cols)] def find(self, r, c): if self.parent[r][c] ! (r, c): pr, pc self.parent[r][c] self.parent[r][c] self.find(pr, pc) return self.parent[r][c] def union(self, r1, c1, r2, c2): root1 self.find(r1, c1) root2 self.find(r2, c2) if root1 ! root2: self.parent[root2[0]][root2[1]] root1对于超大网格可以进一步优化内存使用比如使用哈希表存储非默认父节点或者使用位压缩技术存储坐标。4.3 并行并查集算法在大规模数据处理中并行化的并查集算法可以显著提升性能。一种常见的策略是分阶段处理分区阶段将数据分割为多个独立块在每个块内并行执行部分合并连接阶段合并跨分区的连接关系压缩阶段并行执行路径压缩from multiprocessing import Pool class ParallelDSU: def __init__(self, n): self.parent list(range(n)) self.lock [False] * n def find(self, x): while self.parent[x] ! x: grandparent self.parent[self.parent[x]] # 使用CAS(Compare-And-Swap)实现无锁路径压缩 if self._compare_and_swap(x, self.parent[x], grandparent): x grandparent else: x self.parent[x] return x def _compare_and_swap(self, idx, expected, new): 模拟原子操作 if self.parent[idx] expected: self.parent[idx] new return True return False def parallel_union(self, edges, workers4): 并行处理大量union操作 with Pool(workers) as p: # 第一阶段分区内部合并 chunk_size len(edges) // workers 1 chunks [edges[i:ichunk_size] for i in range(0, len(edges), chunk_size)] p.map(self._process_chunk, chunks) # 第二阶段处理跨分区连接 cross_edges self._collect_cross_edges(edges) p.map(self._process_chunk, [cross_edges]) def _process_chunk(self, edges): for x, y in edges: self.union(x, y) def _collect_cross_edges(self, edges): # 实现略收集连接不同分区的边 return []4.4 内存优化技巧对于超大规模数据集如社交网络分析并查集的内存占用可能成为瓶颈。以下是一些优化技巧位压缩父节点指针如果父节点索引可以用更小的数据类型表示使用numpy数组或特定类型数组import numpy as np class CompactDSU: def __init__(self, n): # 使用uint16节省空间最大支持65535个元素 self.parent np.arange(n, dtypenp.uint16)稀疏存储对于大部分元素直接指向根的稀疏结构只存储非默认父节点class SparseDSU: def __init__(self, n): self.default_parent None # 可以是0或-1等 self.parent {} # 只存储非默认父节点 def find(self, x): if x not in self.parent: return x if self.parent[x] ! x: self.parent[x] self.find(self.parent[x]) return self.parent[x]磁盘持久化对于无法全部装入内存的超大数据设计基于磁盘的并查集利用内存映射文件等技术性能权衡在内存优化和速度之间需要权衡。位压缩通常不影响速度而稀疏存储会减慢查找但节省大量内存。根据实际数据特征选择合适策略。
1. 并查集基础从连通性问题到高效解决方案在计算机科学中处理元素分组和连通性问题是许多算法的基础需求。想象你正在管理一个大型社交网络需要快速判断两个人是否属于同一个朋友圈或者需要将两个原本独立的圈子合并——这正是并查集(Disjoint Set Union, DSU)的用武之地。并查集是一种树型数据结构用于处理不相交集合的合并与查询问题。它的核心操作可以用三个函数来描述make_set(x)创建一个只包含元素x的新集合find(x)找到x所属集合的代表元素也称为根union(x, y)合并包含x和y的两个集合基础实现中我们通常使用数组来存储每个元素的父节点指针。初始时每个元素都是自己的父节点即自己是自己的代表。find操作通过不断追溯父节点直到找到根节点而union操作则将两个集合的根节点连接起来。class DSU: 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): x_root self.find(x) y_root self.find(y) if x_root ! y_root: self.parent[y_root] x_root这种朴素实现的最坏时间复杂度是O(n)的因为树可能会退化成链表。但通过两种优化技术——路径压缩和按秩合并——我们可以达到近乎常数时间的效率。路径压缩在find操作中实现当我们查找某个元素的根时顺便将该元素直接指向根扁平化树结构def find(self, x): if self.parent[x] ! x: self.parent[x] self.find(self.parent[x]) # 路径压缩 return self.parent[x]按秩合并则在union操作中保持树的平衡总是将较小的树合并到较大的树下def __init__(self, n): self.parent list(range(n)) self.rank [0] * n # 初始秩为0 def union(self, x, y): x_root self.find(x) y_root self.find(y) if x_root y_root: return # 按秩合并 if self.rank[x_root] self.rank[y_root]: self.parent[x_root] y_root else: self.parent[y_root] x_root if self.rank[x_root] self.rank[y_root]: self.rank[x_root] 1这两种优化技术共同作用使得并查集的每个操作平均时间复杂度降低到O(α(n))其中α是阿克曼函数的反函数对于任何实际应用中可能遇到的n值α(n)都不会超过5因此可以认为是近乎常数时间。提示在实际编码面试中路径压缩单独使用已经足够高效且实现更简单。按秩合并虽然理论上更优但代码复杂度增加除非特别要求通常路径压缩就是够用的选择。并查集的应用场景非常广泛从图的连通分量检测如Kruskal最小生成树算法、图像处理中的区域标记到社交网络中的好友关系管理。它的高效性尤其适合处理动态连通性问题——即集合结构会随着操作不断变化的场景。2. 带权并查集维护元素间的相对关系标准并查集只能告诉我们元素是否属于同一集合但很多时候我们需要知道集合内元素之间的具体关系。这就是带权并查集(Weighted DSU)的用武之地——它在保持高效的同时还能维护元素间的相对关系。带权并查集的核心思想是为每个节点到其父节点的边赋予一个权值这个权值表示两个元素之间的关系。在find操作进行路径压缩时我们需要同时维护这些权值的正确性在union操作合并集合时需要根据具体问题确定如何合并权值。以经典的食物链问题为例POJ 1182动物之间存在A吃B、B吃C、C吃A的循环关系。我们需要判断给定的关系是否与之前的信息矛盾。这时可以用带权并查集其中权值表示当前节点与父节点的关系0同类1吃父节点2被父节点吃。class WeightedDSU: def __init__(self, n): self.parent list(range(n)) self.relation [0] * n # 0: 同类, 1: 吃父节点, 2: 被父节点吃 def find(self, x): if self.parent[x] ! x: orig_parent self.parent[x] self.parent[x] self.find(self.parent[x]) # 路径压缩 # 更新关系当前节点与根的关系 (当前与原父关系 原父与根关系) % 3 self.relation[x] (self.relation[x] self.relation[orig_parent]) % 3 return self.parent[x] def union(self, x, y, rel): rel: x与y的关系 (0: 同类, 1: x吃y, 2: x被y吃) x_root self.find(x) y_root self.find(y) if x_root y_root: return False # 无需合并 # 将y_root合并到x_root下 self.parent[y_root] x_root # 更新关系通过向量计算确定新的关系 # x-x_root: relation[x], y-y_root: relation[y], x与y: rel # 需要找到y_root-x_root的关系 self.relation[y_root] (self.relation[x] - rel - self.relation[y]) % 3 return True另一个典型应用是解决等式方程问题如LeetCode 990。给定一组形如ab或a!b的方程判断它们是否矛盾。我们可以用带权并查集其中权值表示两个变量的差值class EquationDSU: def __init__(self): self.parent {} self.weight {} # parent[x] y时weight[x]表示x - y的值 def find(self, x): if x not in self.parent: self.parent[x] x self.weight[x] 0.0 return x if self.parent[x] ! x: orig_parent self.parent[x] self.parent[x] self.find(self.parent[x]) self.weight[x] self.weight[orig_parent] return self.parent[x] def union(self, x, y, value): value表示x - y的值 x_root self.find(x) y_root self.find(y) if x_root y_root: return abs(self.weight[x] - self.weight[y] - value) 1e-5 # 合并两个集合 self.parent[x_root] y_root self.weight[x_root] self.weight[y] value - self.weight[x] return True带权并查集的关键在于定义清晰的权值含义差、比值、特定关系等在路径压缩时正确维护权值的传递性在合并集合时正确处理权值的组合关系注意权值的更新公式通常需要根据具体问题推导。一个实用技巧是画向量图——将每个关系看作向量通过向量加减来确定合并后的新关系。3. 扩展域并查集用空间换逻辑清晰度当带权并查集的权值关系变得复杂时另一种解决方案是扩展域并查集(Extended Domain DSU)也称为种类并查集。它的核心思想是将每个元素拆分为多个逻辑节点通过在不同域中的连接关系来表达复杂的约束条件。扩展域并查集特别适合处理敌人的敌人是朋友这类逻辑关系。以经典的团伙问题为例已知一些人是朋友相互认识一些人是敌人相互不认识且朋友的朋友是朋友敌人的敌人也是朋友。判断最多可能有多少个独立的团伙。在这种情况下我们可以将每个人的信息拆分为两个域域A表示朋友关系域B表示敌人关系具体实现时对于元素x我们用x表示其朋友域xn表示其敌人域n是总元素数。当x和y是朋友时我们合并x和y同时合并xn和yn当x和y是敌人时我们合并x和yn同时合并y和xn。class ExtendedDSU: def __init__(self, n): self.parent list(range(2 * n)) # 前n个是朋友域后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, x, y, is_friend): if is_friend: # 朋友关系合并x和y以及xn和yn self.parent[self.find(x)] self.find(y) self.parent[self.find(x n)] self.find(y n) else: # 敌人关系合并x和yn以及y和xn self.parent[self.find(x)] self.find(y n) self.parent[self.find(y)] self.find(x n) def is_conflict(self, x, y, is_friend): if is_friend: # 检查x和yn是否在同一集合即x和y是否是敌人 return self.find(x) self.find(y n) else: # 检查x和y是否在同一集合即x和y是否是朋友 return self.find(x) self.find(y)扩展域并查集相比带权并查集的优点是逻辑更加清晰直观特别是在关系类型较多的情况下。例如处理三种关系朋友、敌人、中立时可以扩展为三个域class ThreeRelationDSU: def __init__(self, n): self.parent list(range(3 * n)) # 0~n-1:朋友域, n~2n-1:敌人域, 2n~3n-1:中立域 def set_relation(self, x, y, relation): relation: 0-朋友, 1-敌人, 2-中立 if relation 0: self.union(x, y) self.union(x n, y n) self.union(x 2 * n, y 2 * n) elif relation 1: self.union(x, y n) self.union(x n, y 2 * n) self.union(x 2 * n, y) else: self.union(x, y 2 * n) self.union(x n, y) self.union(x 2 * n, y n)扩展域并查集的空间复杂度是O(kn)其中k是关系类型数。虽然比带权并查集的O(n)要高但在处理复杂关系时代码的可读性和可维护性往往更好。选择哪种实现取决于具体问题和个人偏好。实战技巧当关系类型超过3种时带权并查集通常更合适。而对于二值关系是/否朋友/敌人等扩展域实现往往更简单不易出错。4. 并查集的高级应用与性能优化并查集在实际工程中的应用远比基础算法题目丰富。让我们探讨几个高级应用场景和相应的优化技巧。4.1 动态图的连通性维护在需要实时维护图连通性的场景中如网络拓扑管理传统的DFS/BFS方法在每次边增删后都需要重新计算效率低下。使用并查集可以高效处理边的添加但标准实现无法处理删除操作。可删点并查集通过引入虚节点技术解决这一问题class DeletableDSU: def __init__(self, n): self.parent list(range(2 * n)) # 前n个是实际节点后n个是虚节点 self.real list(range(n)) # 实际节点到虚节点的映射 self.next_virtual n # 下一个可用的虚节点 def find(self, x): x self.real[x] if self.parent[x] ! x: self.parent[x] self.find(self.parent[x]) return self.parent[x] def union(self, x, y): x_root self.find(x) y_root self.find(y) if x_root ! y_root: self.parent[y_root] x_root def delete(self, x): 删除节点x为其分配一个新的虚节点 self.real[x] self.next_virtual self.parent[self.next_virtual] self.next_virtual self.next_virtual 1这种技术通过为每个删除操作创建新的虚节点来保持原有连接关系代价是空间复杂度增加。对于频繁删除的场景可以考虑更复杂的基于时间戳的区间并查集。4.2 二维网格问题的并查集优化在处理二维网格如图像处理、游戏地图时常规的并查集需要对每个网格点进行线性编号。更高效的做法是利用网格的局部性实现基于块的路径压缩class GridDSU: def __init__(self, rows, cols): self.rows rows self.cols cols self.parent [(r, c) for r in range(rows) for c in range(cols)] def find(self, r, c): if self.parent[r][c] ! (r, c): pr, pc self.parent[r][c] self.parent[r][c] self.find(pr, pc) return self.parent[r][c] def union(self, r1, c1, r2, c2): root1 self.find(r1, c1) root2 self.find(r2, c2) if root1 ! root2: self.parent[root2[0]][root2[1]] root1对于超大网格可以进一步优化内存使用比如使用哈希表存储非默认父节点或者使用位压缩技术存储坐标。4.3 并行并查集算法在大规模数据处理中并行化的并查集算法可以显著提升性能。一种常见的策略是分阶段处理分区阶段将数据分割为多个独立块在每个块内并行执行部分合并连接阶段合并跨分区的连接关系压缩阶段并行执行路径压缩from multiprocessing import Pool class ParallelDSU: def __init__(self, n): self.parent list(range(n)) self.lock [False] * n def find(self, x): while self.parent[x] ! x: grandparent self.parent[self.parent[x]] # 使用CAS(Compare-And-Swap)实现无锁路径压缩 if self._compare_and_swap(x, self.parent[x], grandparent): x grandparent else: x self.parent[x] return x def _compare_and_swap(self, idx, expected, new): 模拟原子操作 if self.parent[idx] expected: self.parent[idx] new return True return False def parallel_union(self, edges, workers4): 并行处理大量union操作 with Pool(workers) as p: # 第一阶段分区内部合并 chunk_size len(edges) // workers 1 chunks [edges[i:ichunk_size] for i in range(0, len(edges), chunk_size)] p.map(self._process_chunk, chunks) # 第二阶段处理跨分区连接 cross_edges self._collect_cross_edges(edges) p.map(self._process_chunk, [cross_edges]) def _process_chunk(self, edges): for x, y in edges: self.union(x, y) def _collect_cross_edges(self, edges): # 实现略收集连接不同分区的边 return []4.4 内存优化技巧对于超大规模数据集如社交网络分析并查集的内存占用可能成为瓶颈。以下是一些优化技巧位压缩父节点指针如果父节点索引可以用更小的数据类型表示使用numpy数组或特定类型数组import numpy as np class CompactDSU: def __init__(self, n): # 使用uint16节省空间最大支持65535个元素 self.parent np.arange(n, dtypenp.uint16)稀疏存储对于大部分元素直接指向根的稀疏结构只存储非默认父节点class SparseDSU: def __init__(self, n): self.default_parent None # 可以是0或-1等 self.parent {} # 只存储非默认父节点 def find(self, x): if x not in self.parent: return x if self.parent[x] ! x: self.parent[x] self.find(self.parent[x]) return self.parent[x]磁盘持久化对于无法全部装入内存的超大数据设计基于磁盘的并查集利用内存映射文件等技术性能权衡在内存优化和速度之间需要权衡。位压缩通常不影响速度而稀疏存储会减慢查找但节省大量内存。根据实际数据特征选择合适策略。
![[具身智能-181]：PC+服务器+具身机器人：构建具身智能从仿真到量产的闭环迭代混合架构](http://pic.xiahunao.cn/yaotu/[具身智能-181]：PC+服务器+具身机器人：构建具身智能从仿真到量产的闭环迭代混合架构)
