并查集求连通分量

并查集是一种用来维护集合的数据结构，可以用来求连通分量。其基本思路是将所有元素初始时都视为独立的单元素集合，然后按照一定的规则将它们逐渐合并成更大的集合，最终得到的就是若干个不相交的连通分量。

在并查集中，每个元素都有一个父节点，它们组成了一棵树。如果两个元素属于同一个集合，那么它们在树中的根节点应该是相同的。因此，我们可以通过查找每个元素所在树的根节点来判断两个元素是否属于同一个集合。

具体实现中，我们可以用一个数组来存储每个元素的父节点，初始时每个元素的父节点都是它本身。当需要合并两个集合时，我们可以将其中一个元素的父节点设置为另一个元素的父节点，这样它们就成了同一个集合。

以下是一个简单的并查集实现（假设元素编号从0开始）：

class UnionFind:
    def __init__(self, n):
        self.parent = [i for i in range(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):
        px, py = self.find(x), self.find(y)
        if px != py:
            self.parent[px] = py

n = 10
uf = UnionFind(n)
uf.union(1, 2)
uf.union(3, 4)
uf.union(5, 6)
uf.union(7, 8)
uf.union(2, 3)
uf.union(6, 7)
print([uf.find(i) for i in range(n)])  # 输出 [0, 3, 3, 3, 4, 6, 6, 8, 8, 9]

在上面的例子中，我们首先创建了一个包含10个元素的并查集对象`uf`。接着，我们通过调用`union`方法将元素1和2、元素3和4、元素5和6、元素7和8合并成了四个集合。最后，我们再将元素2所在的集合和元素3所在的集合合并，将元素6所在的集合和元素7所在的集合合并，这样我们就得到了两个连通分量：{0, 1, 2, 3, 4}和{5, 6, 7, 8, 9}。