python实现并查集

在Python中，我们可以使用内置的数据结构如集合（set）或者自定义类来实现并查集数据结构。并查集是一种常用的数据结构，用于处理一些集合相关的操作，比如查找、合并等。以下是使用自定义类简单实现的一个示例：

class UnionFind:
    def __init__(self, n):
        self.id = list(range(n))
        
    # 查找根节点
    def find(self, x):
        if self.id[x] != x:
            self.id[x] = self.find(self.id[x])
        return self.id[x]
    
    # 合并两个集合
    def union(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x != root_y:
            self.id[root_x] = root_y

# 使用示例
uf = UnionFind(5)  # 初始化一个包含5个元素的并查集
uf.union(0, 1)  # 合并第0和1个元素的集合
uf.union(3, 4)  # 合并第3和4个元素的集合
print(uf.find(0))  # 查看0是否与1在一个集合里，结果会是1

在这个例子中，`find`函数用于查找某个元素所在的集合的根节点，如果它不是根节点，则继续向上查找，直到找到根节点。`union`函数则负责将两个集合合并到一起。