python实现union类

在Python中，可以通过类来实现union，具体实现方法如下：

class Union:
    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):
        i_root = self.find(i)
        j_root = self.find(j)
        if i_root == j_root:
            return
        if self.rank[i_root] < self.rank[j_root]:
            self.parent[i_root] = j_root
        elif self.rank[i_root] > self.rank[j_root]:
            self.parent[j_root] = i_root
        else:
            self.parent[j_root] = i_root
            self.rank[i_root] += 1

在这个Union类中，我们使用了两个数组来表示每个元素的父节点和每个集合的秩。其中，`parent`数组用来表示每个元素的父节点，初始时每个元素的父节点都是它自己。`rank`数组用来表示每个集合的秩，即树的高度。

`find`方法用来查找元素i所在的集合的根节点，并且在查找的过程中将路径上的所有节点的父节点都更新为根节点，这样可以减少后续查找的时间。`union`方法用来将元素i所在的集合和元素j所在的集合合并起来，具体合并的方式是比较两个集合的秩，将秩小的集合的根节点指向秩大的集合的根节点。如果两个集合的秩相同，那么将其中一个集合的根节点指向另一个集合的根节点，并且将被指向的集合的秩加1。

使用这个Union类可以方便地实现一些与集合有关的算法，比如Kruskal最小生成树算法、并查集算法等。