并查集 rank 的优化

并查集 rank 的优化

并查集是一种数据结构，用于处理一些不交集的合并及查询问题。它支持两种操作：查找（Find）和合并（Union）。查找操作用于确定某个元素属于哪个集合，而合并操作用于将两个集合合并成一个。并查集在处理如连通性问题、图的动态连通性等场景时非常有用。

并查集的基本原理

并查集的基本思想是，初始时，每个元素构成一个单独的集合，每个集合用一棵树来表示。树中的每个节点都有一个指针指向其父节点，根节点的父节点指针指向自己。在合并操作中，将一棵树的根节点指向另一棵树的根节点，从而实现两个集合的合并。在查找操作中，通过遍历父节点指针，找到某个元素的根节点，从而确定该元素所在的集合。

rank 优化

在并查集的实现中，rank 优化是一种常见的优化策略，用于提高并查集的效率。rank 优化的基本思想是，在合并操作中，总是将较小的树合并到较大的树上。这样，可以避免树的高度过高，从而减少查找操作的时间复杂度。

具体来说，每个节点除了有一个指向父节点的指针外，还有一个 rank 值，表示该节点所在树的秩（高度）。在合并操作中，比较两个根节点的 rank 值，将 rank 值较小的根节点指向 rank 值较大的根节点。如果两个根节点的 rank 值相等，则选择其中一个作为新的根节点，并将其 rank 值加 1。

rank 优化的实现

以下是 rank 优化的并查集的 Python 实现：

class UnionFind:def __init__(self, n):self.p