并查集 size 的优化学习笔记

1. 什么是并查集

并查集（Disjoint-set Union）是一种树型的数据结构，用于处理一些不相交（Disjoint Sets）集合（Union Sets）的合并及查询问题。通常用于解决动态连通性问题。

2. 并查集的实现

并查集可以使用数组或者链表来实现，其中数组实现较为常用。具体实现时，我们将每个元素看作一个节点，节点之间通过父子关系建立起一棵树。

在初始状态下，每个节点都是一个独立的集合，且它们的父指针都指向自己。当我们需要合并两个集合时，只需要将其中一个集合的根节点的父指针指向另一个集合的根节点即可完成合并操作。

同时，在查找某个节点所属集合的过程中，我们可以通过沿着父指针不断往上找，直到找到根节点为止，这样就可以快速知道某个节点所属的集合了。

3. 并查集 size 的优化

默认情况下，我们可以将某个集合的根节点的父指针指向另一个集合的根节点，这样就完成了两个集合的合并。但是这样做有一个问题，即可能会导致某些树的深度过大，从而降低程序的效率。

为了解决这个问题，我们可以引入一个 size 数组，用于记录每个集合的大小。在合并两个集合时，我们总是将元素较少的那个集合合并到元素较多的那个集合中，这样可以保证树的深度不会过大。

同时，在查找某个节点所属集合的过程中，我们可以通过路径压缩来优化程序的效率。具体来说，当我们查询某个节点所属集合时，我们沿着父指针一路往上找到它的根节点，并将沿途经过的所有节点的父指针都直接指向根节点，这样可以减小树的深度，从而提高程序的效率。

4. 实例

以下是一个使用并查集进行连通性判断的示例代码：

pythonCopy Code
class UnionFind:
    def __init__(self, n):
        self.parent = [i for i in range(n)]
        self.size = [1] * 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):
        root_x, root_y = self.find(x), self.find(y)
        if root_x == root_y:
            return False
        if self.size[root_x] < self.size[root_y]:
            root_x, root_y = root_y, root_x
        self.parent[root_y] = root_x
        self.size[root_x] += self.size[root_y]
        return True

以上代码实现了一个基本的并查集，其中使用了 size 数组来进行优化，并且在 find 操作中使用了路径压缩来提高程序的效率。

使用以上代码可以轻松解决一些动态连通性问题，比如寻找连通块、检测图中是否有环等问题。