并查集的代码

以下是一个简单的并查集实现：

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:
            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:
            return
        if self.rank[x_root] < self.rank[y_root]:
            self.parent[x_root] = y_root
        elif self.rank[x_root] > self.rank[y_root]:
            self.parent[y_root] = x_root
        else:
            self.parent[y_root] = x_root
            self.rank[x_root] += 1

在这个实现中，我们使用两个数组来保存每个节点的父节点和秩。在初始化时，每个节点的父节点都是它自己，秩为0。find方法用于查找给定节点的根节点，使用路径压缩来加速查找过程。union方法用于将两个节点所在的集合合并，使用秩来避免树的深度过大，从而保证操作的时间复杂度。