并查集python代码

以下是一个基本的并查集 Python 代码实现：

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, i):
        if self.parent[i] != i:
            self.parent[i] = self.find(self.parent[i])
        return self.parent[i]

    def union(self, i, j):
        pi, pj = self.find(i), self.find(j)
        if pi == pj:
            return False

        if self.rank[pi] < self.rank[pj]:
            pi, pj = pj, pi

        self.parent[pj] = pi
        if self.rank[pi] == self.rank[pj]:
            self.rank[pi] += 1

        return True

使用方法：

uf = UnionFind(5)  # 创建一个有 5 个元素的并查集

uf.union(0, 1)  # 将元素 0 和元素 1 合并到同一个集合中
uf.union(2, 3)  # 将元素 2 和元素 3 合并到同一个集合中
uf.union(1, 2)  # 将元素 1 和元素 2 合并到同一个集合中

print(uf.find(0))  # 输出元素 0 所在的集合的代表元素
print(uf.find(3))  # 输出元素 3 所在的集合的代表元素

输出：

1
2