并查集python实现

以下是Python实现的简单并查集：

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n
        self.count = n

    def find(self, x):
        while x != self.parent[x]:
            self.parent[x] = self.parent[self.parent[x]]
            x = self.parent[x]
        return x

    def union(self, p, q):
        root_p = self.find(p)
        root_q = self.find(q)
        if root_p == root_q:
            return
        if self.size[root_p] > self.size[root_q]:
            self.parent[root_q] = root_p
            self.size[root_p] += self.size[root_q]
        else:
            self.parent[root_p] = root_q
            self.size[root_q] += self.size[root_p]
        self.count -= 1

    def connected(self, p, q):
        return self.find(p) == self.find(q)

其中，`parent`数组记录每个节点的父节点，`size`数组记录每个集合的大小，`count`表示有多少个不同的集合。`find`函数用于查找一个节点所属的集合，`union`函数用于合并两个集合，`connected`函数用于判断两个节点是否在同一集合中。