＜数据结构＞并查集

**数据结构：并查集**

并查集（Union-Find）是一种用于管理一个集合中元素的分组关系的数据结构。它允许你将两个或多个元素合并为一个分组，并且可以快速判断两个元素是否属于同一个分组。

### 并查集的基本概念并查集通常由以下几个部分组成：

* **父节点数组**：用于存储每个元素的父节点信息。初始时，每个元素都是自己的父节点。
* **大小数组**：用于存储每个分组中的元素数量。

### 并查集的基本操作并查集支持以下几个基本操作：

* **Find(x)**：找到元素x所在的分组的代表元素除外* **Union(x, y)**：将元素x和y所在的分组合并为一个分组。

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

class UnionFind:
 def __init__(self, n):
 self.parent = list(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 = self.find(x)
 root_y = self.find(y)

 if root_x != root_y:
 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]

# 示例使用uf = UnionFind(5)
print(uf.find(0)) # 输出：0print(uf.find(1)) # 输出：1uf.union(0,2) # 将0和2合并为一个分组print(uf.find(0)) # 输出：0print(uf.find(2)) # 输出：0