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: if self.size[root_x] > self.size[root_y]: self.parent[root_y] = root_x self.size[root_x] += self.size[root_y] else: self.parent[root_x] = root_y self.size[root_y] += self.size[root_x] n = 10 uf = UnionFind(n) # 执行随机的union和find操作 import random for i in range(10): x, y = random.randint(0, n-1), random.randint(0, n-1) uf.union(x, y) print(uf.parent, uf.size) x, y = random.randint(0, n-1), random.randint(0, n-1) print(uf.find(x) == uf.find(y))

这段代码实现了一个并查集数据结构。并查集可以用来维护一个集合的划分，支持以下两种操作：

1. 查找某个元素所属的集合的代表元素。
2. 合并两个集合，即将两个集合合并成一个。

在这段代码中，构造函数初始化了一个数组 parent 和一个数组 size，分别表示每个元素的父节点和以该元素为根节点的集合的大小。在 find 操作中，使用路径压缩优化，将元素的父节点更新为其所属集合的代表元素，以加速后续的查询操作。在 union 操作中，首先查找两个元素所属的集合的代表元素，然后将两个代表元素所属的集合合并，将其中一个代表元素的父节点更新为另一个代表元素，并更新集合的大小。最后，代码使用随机数执行了若干次随机的 union 和 find 操作，并输出了每个元素的父节点和集合的大小，以及两个元素是否属于同一个集合。