python实现并查集类

并查集（Disjoint-set Forest）是一种数据结构，用于维护不相交集合的抽象表示。在Python中，我们可以使用字典（`dict`）或者类来实现一个基本的并查集。这里我为你提供一个简单的类定义：

class DisjointSet:
    def __init__(self, elements=None):
        if elements is None:
            self.parent = {i: i for i in range(max(0, len(elements) - 1) + 1)}
        else:
            self.parent = {i: i for i in elements}

    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:
            self.parent[root_x] = root_y

    def connected(self, x, y):
        """检查x和y是否在同一集合内"""
        return self.find(x) == self.find(y)

这个类包含三个主要方法：

1. `find(x)`：查找元素`x`的根节点，如果`x`不是根节点则进行路径压缩（路径上所有节点都指向根）。
2. `union(x, y)`：合并两个集合，通过求它们的根节点并将其连接起来。
3. `connected(x, y)`：判断`x`和`y`是否在同一集合中。

使用示例：

ds = DisjointSet([0, 1, 2, 3, 4])
ds.union(0, 1)  # 合并第一个和第二个元素
print(ds.connected(0, 1))  # 输出：True

ds.union(2, 3)  # 合并第三个和第四个元素
print(ds.connected(2, 3))  # 输出：True

print(ds.connected(0, 4))  # 输出：False，因为0和4不在同一个集合