并查集 rank 优化

算法思路

并查集（Union-Find）算法是一种用于解决连通性问题的算法。在最坏情况下，该算法可以在 $O(n^2)$ 的时间复杂度下执行。

并查集算法主要包含两个操作：合并（Union）和查找（Find）。其中合并操作将两个不相交的集合合并为一个集合，而查找操作则将一个元素所属的集合进行查找。

在并查集算法中，我们使用树结构来表示每个集合，其中每个节点表示一个元素，而每个集合的根节点需要记录该集合所包含的元素个数。这样可以确保在进行合并操作时，较小的集合总是被合并进较大的集合中去。

优化

尽管并查集算法已经很快了，但是它仍然可以进行一些优化。其中一种优化方法是使用 rank 来记录树的高度。这种优化称为 rank 优化。

rank 优化的实现非常简单。我们只需要在每个节点上记录一个 rank 值，用于表示从该节点向下的子树的高度。当我们进行合并操作时，我们总是将较矮的树合并到较高的树上，以确保树的高度始终最小化。

代码实现

下面是使用 Python 实现 rank 优化的并查集算法的代码：

pythonCopy Code
class UnionFind:
    def __init__(self, n: int):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x: int) -> int:
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x: int, y: int) -> None:
        root_x, root_y = self.find(x), self.find(y)
        if root_x == root_y:
            return
        if self.rank[root_x] < self.rank[root_y]:
            self.parent[root_x] = root_y
        elif self.rank[root_x] > self.rank[root_y]:
            self.parent[root_y] = root_x
        else:
            self.parent[root_x] = root_y
            self.rank[root_y] += 1

实例

下面是一个使用 rank 优化的并查集算法解决连通性问题的实例。

假设我们有 $n$ 个节点，它们的编号分别为 $0, 1, \ldots, n-1$。我们需要对这 $n$ 个节点进行分组，使得每组中的节点之间都是连通的。为了实现这个目标，我们可以依次添加边，并在添加每一条边之后检查图是否连通。如果图连通，则我们可以停止添加边，并输出结果。

下面是使用 rank 优化的并查集算法实现上述问题的代码：

pythonCopy Code
def find_cycle(edges):
    n = max(max(e) for e in edges)
    uf = UnionFind(n + 1)

    for u, v in edges:
        if uf.find(u) == uf.find(v):
            return u, v
        uf.union(u, v)

edges = [(0, 1), (1, 2), (2, 0), (3, 4), (4, 5), (5, 6), (6, 4)]
u, v = find_cycle(edges)
print(f"({u}, {v}) form a cycle")

在上述代码中，我们通过传入一个边的列表来表示图。我们首先创建一个 UnionFind 对象，然后依次添加每条边。在添加每条边时，我们判断该边连接的两个节点是否已经处于同一个集合中。如果是，则说明添加该边会形成一个环；否则，我们将该边加入到集合中，并继续添加下一条边。最终，我们可以得到两个节点 $u$ 和 $v$，它们形成了一个环。

Tip：在使用 rank 优化的并查集算法时，我们需要特别注意合并操作的顺序。具体来说，我们应该总是将较矮的树合并到较高的树上去，以确保树的高度尽可能小。