写一个并查集的模板代码

### 回答1：

这是一个基本的并查集模板代码：class UnionFind:
def __init__(self, n):
self.par = [i for i in range(n)]
self.size = [1] * n def find(self, x):
if self.par[x] == x:
return x
else:
self.par[x] = self.find(self.par[x])
return self.par[x] def unite(self, x, y):
x = self.find(x)
y = self.find(y)
if x == y:
return
if self.size[x] < self.size[y]:
self.par[x] = y
self.size[y] += self.size[x]
else:
self.par[y] = x
self.size[x] += self.size[y]

### 回答2：
并查集是一种常用的数据结构，用于解决连接问题和集合合并问题。以下是一个并查集的模板代码：

class UnionFind:
    def __init__(self, n):
        # 初始化节点的根节点为自身
        self.parent = [i for i in range(n)]
        # 初始化每个节点的rank（高度）为1
        self.rank = [1] * n

    def find(self, x):
        # 查找x的根节点
        if x != self.parent[x]:
            # 路径压缩，将x的父节点直接设为根节点
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        # 将x和y所在的集合合并
        root_x = self.find(x)
        root_y = self.find(y)
        # 如果两个节点已经在同一个集合中，则无需合并
        if root_x == root_y:
            return
        # 将rank较小的根节点连接到rank较大的根节点上
        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

    def is_connected(self, x, y):
        # 判断x和y是否连接在同一个集合中
        return self.find(x) == self.find(y)

以上是一个基本的并查集的模板代码。我们可以通过初始化函数`__init__`来创建并查集，并通过`union`函数将两个集合合并，`find`函数查找节点的根节点，`is_connected`函数判断两个节点是否连接在同一个集合中。

并查集的主要思想是将每个节点看作一个集合，通过合并操作将具有连接关系的节点归并到同一个集合中，并通过路径压缩和按秩合并优化获取更高效的查询操作。