并查集快速合并

并查集快速合并

并查集是一种数据结构，用于处理一些不交集的合并及查询问题。它支持两种操作：查找（Find）和合并（Union）。查找操作用于确定某个元素属于哪个子集，而合并操作用于将两个子集合并成一个集合。并查集在很多算法问题中都有应用，比如求解无向图的连通分量、检测图中是否存在环等。

在并查集中，实现快速合并是提高效率的关键。本文将详细介绍并查集的快速合并方法，包括路径压缩和按秩合并两种优化技术。

路径压缩

路径压缩是并查集的一种优化技术，用于在执行查找操作时减少树的高度。其基本思想是在查找过程中，将沿途的所有节点直接连接到根节点上。这样，下次再进行查找时，路径就会变得更短，从而提高了查找的效率。

路径压缩的实现非常简单，只需在查找操作中添加一行代码即可。具体来说，当我们在查找某个节点的根节点时，我们可以将沿途经过的所有节点的父节点设置为根节点。这样，下次再查找这些节点时，就可以直接找到根节点，而不需要经过中间节点。

按秩合并

按秩合并是并查集的另一种优化技术，用于在执行合并操作时减少树的高度。其基本思想是在合并两个集合时，总是将较小的树合并到较大的树上。这样，树的高度就不会无限增长，从而提高了合并的效率。

在实现按秩合并时，我们需要为每个节点维护一个秩（rank）属性，表示该节点所在树的高度。在合并两个集合时，我们比较两个根节点的秩，将秩较小的树合并到秩较大的树上，并将合并后的树的秩更新为较大的秩加一（如果两个根节点的秩相同，则可以选择任意一个作为新的根节点，并将其秩加一）。

完整代码示例

下面是一个使用路径压缩和按秩合并优化的并查集的Python代码示例：

class UnionFind:
    def __init__(self, n):
        self.parent = [i for i in range(n)]
        self.rank = [0] * 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):
        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

# 使用示例
uf = UnionFind(10)
uf.union(0, 1)
uf.union(1, 2)
uf.union(3, 4)
uf.union(4, 5)
print(uf.find(0))  # 输出: 0
print(uf.find(2))  # 输出: 0
print(uf.find(3))  # 输出: 3
uf.union(0, 3)
print(uf.find(3))  # 输出: 0

在这个示例中，我们创建了一个包含10个节点的并查集。我们首先合并了节点0和节点1，然后合并了节点1和节点2，依此类推。在执行查找操作时，我们可以看到路径压缩的效果，例如uf.find(2)直接返回了根节点0。在执行合并操作时，我们可以看到按秩合并的效果，例如uf.union(0, 3)将较小的树（以节点3为根的树）合并到较大的树（以节点0为根的树）上。

通过路径压缩和按秩合并这两种优化技术，我们可以大大提高并查集的效率，使其在最坏情况下的时间复杂度接近于线性。