并查集快速合并学习笔记

并查集是一种用于处理集合的数据结构，它支持合并（Union）和查找（Find）操作。这个数据结构非常适用于连通性问题，例如判断两个点是否在一个连通块中。

实现并查集

并查集可以用数组和树两种方式来实现。

基于数组的实现

基于数组的实现相对简单，可以使用一个长度为 $n$ 的数组来记录每个元素的父节点。初始时，每个元素的父节点都指向自己。当两个元素需要合并时，我们只需将其中一个元素的父节点指向另一个元素即可。

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

基于树的实现

基于树的实现可以优化查询的时间复杂度。具体来说，我们可以让每个节点的父指针指向它的根节点，从而压缩树的高度。初始化时，每个节点的父指针都指向它自己。合并时，我们将其中一棵树的根节点指向另一棵树的根节点即可。

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

示例

以下是一个使用并查集验证图中是否存在环的示例：

pythonCopy Code
class Solution:
    # 判断无向图中是否存在环
    def hasCycle(self, n: int, edges: List[List[int]]) -> bool:
        uf = UnionFind(n)
        for edge in edges:
            x = edge[0]
            y = edge[1]
            if uf.find(x) == uf.find(y):
                return True
            uf.union(x, y)
        return False

在这个示例中，我们使用了基于树的实现，并将其封装成了一个类。输入参数 n 表示图中节点的数量，edges 是一个二维数组，每个元素表示图中的一条边。在循环遍历所有的边时，我们使用了并查集来判断节点之间是否存在连通路径，如果两个节点已经处于同一个连通块中，则说明它们之间形成了环。这样，我们就可以通过并查集来验证整个图是否存在环了。