python并查集模板

以下是一个简单的 Python 并查集的模板：

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * 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:
            return

        if self.rank[root_x] < self.rank[root_y]:
            self.parent[root_x] = root_y
        elif self.rank[root_x] > self.rank[root_y]:
            self.parent[root_y] = root_x
        else:
            self.parent[root_y] = root_x
            self.rank[root_x] += 1

# 使用示例
n = 5  # 元素个数
uf = UnionFind(n)

# 进行合并操作
uf.union(0, 1)
uf.union(2, 3)
uf.union(3, 4)

# 查找操作
print(uf.find(1))  # 输出 0，因为 0 和 1 合并在一起
print(uf.find(4))  # 输出 2，因为 2，3，4 合并在一起

这个模板实现了一个基本的并查集数据结构，包括初始化、查找和合并操作。通过 `find` 方法可以找到元素所属的集合代表，通过 `union` 方法可以将两个元素所属的集合合并在一起。