并查集（Union-Find）是一种用于处理不相交集合（Disjoint Set）合并及查询问题的数据结构。它非常高效地支持以下两种操作：

1. 查找（Find）：确定元素属于哪个集合。通常用来判断两个元素是否属于同一集合。
2. 合并（Union）：将两个集合合并成一个集合。

并查集广泛应用于网络连接问题、图的连通性判断、最小生成树算法（如Kruskal算法）等。

基本思想

并查集使用一个数组 parent 来表示集合，其中 parent[i] 为元素 i 的父节点。在初始状态，每个元素都是自身的父节点。

高效操作

为了提高效率，并查集引入了两种优化技术：

1. 路径压缩（Path Compression）：

   • 在执行查找操作时，将路径上所有节点直接连接到根节点。这样可以加快后续查找操作的速度。

2. 按秩合并（Union by Rank）：

   • 合并时，根据树的高度（秩）来决定将哪个树作为另一棵树的子树。这样可以防止树退化为链表，提高效率。

算法实现

class UnionFind:  
    def __init__(self, size):  
        self.parent = list(range(size))  
        self.rank = [1] * size  
    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):  
        rootX = self.find(x)  
        rootY = self.find(y)  
        if rootX != rootY:  
            if self.rank[rootX] > self.rank[rootY]:  
                self.parent[rootY] = rootX  
            elif self.rank[rootX] < self.rank[rootY]:  
                self.parent[rootX] = rootY  
            else:  
                self.parent[rootY] = rootX  
                self.rank[rootX] += 1  
    def connected(self, x, y):  
        return self.find(x) == self.find(y)  
# 示例使用  
uf = UnionFind(10)  
uf.union(1, 2)  
uf.union(2, 3)  
print(uf.connected(1, 3))  # 输出: True  
print(uf.connected(1, 4))  # 输出: False  

时间复杂度

在路径压缩和按秩合并的优化下，并查集的单个操作的时间复杂度几乎是常数时间，近似为 O(α(n))，其中 α 为阿克曼函数的反函数，增长极其缓慢。

应用场景

1. 网络连通性：判断网络中两点是否连通。
2. 最小生成树：Kruskal算法中用来判断添加的边是否会形成环。
3. 动态连通性问题：处理一系列静态图的连通性问题，比如电网、路网等。

并查集是一种强大的工具，可以用以解决很多涉及集合合并和查询的问题，对于理解和实现相关算法非常有帮助。