并查集算法中的等级合并和路径压缩

1. 前言

并查集（Disjoint Set）是一种用于处理连通性问题的数据结构。它支持两个常用操作：合并两个集合和查找元素所在的集合。并查集在实际应用中有着广泛的运用，例如用于社交网络的连通性分析、游戏中的团队匹配等。

在并查集算法中，等级合并和路径压缩是两种常用且有效的优化技巧。本文将对这两种技巧进行详细介绍，并附上实现代码。

2. 算法介绍

2.1 并查集基本操作

并查集维护了一个由若干个集合组成的集族，每个集合用其某个元素（称为代表元）代表。并查集支持以下两种基本操作：

1. `find(x)`：查找元素x所在的集合的代表元。可以通过递归查找来实现，或者使用路径压缩进行优化。

2. `merge(x, y)`：将元素x所在的集合和元素y所在的集合合并为一个集合。可以通过等级合并或者按秩合并进行优化。

2.2 等级合并

等级合并是一种并查集的优化策略，通过维护每个集合的等级来优化`merge`操作。

具体来说，每个集合有一个等级，初始等级为1。合并两个集合时，将等级较小的集合合并到等级较大的集合下面。若两个集合等级相同，则可以将其中一个集合合并到另一个集合下面，同时将另一个集合的等级加一。

这样做的目的是避免将一些原本相对独立的集合过度合并，从而降低后续操作的时间复杂度。由于等级只会随着合并操作而增加，因此并查集中集合的个数是固定的。

等级合并的代码实现如下：

class UnionFind {
public:
    UnionFind(int n): parent(n), rank(n, 1) {
        for (int i = 0; i < n; ++i) {
            parent[i] = i;
        }
    }
    
    int find(int x) {
        if (parent[x] == x) {
            return x;
        }
        return parent[x] = find(parent[x]);
    }
    
    void merge(int x, int y) {
        int px = find(x), py = find(y);
        if (px != py) {
            if (rank[px] < rank[py]) {
                parent[px] = py;
            } else if (rank[px] > rank[py]) {
                parent[py] = px;
            } else {
                parent[px] = py;
                ++rank[py];
            }
        }
    }
    
private:
    vector parent;
    vector rank;
};

2.3 路径压缩

路径压缩是一种并查集的优化策略，通过在查找的过程中，将路径上的所有点都直接连接到集合的代表元上，从而优化`find`操作。

具体来说，每次查找元素x所在的集合时，将路径上所有点都连接到代表元上，这样下一次查找x所在集合时，就可以直接访问代表元，从而减少递归深度和查找时间。

路径压缩的代码实现如下：

class UnionFind {
public:
    UnionFind(int n): parent(n), rank(n, 1) {
        for (int i = 0; i < n; ++i) {
            parent[i] = i;
        }
    }
    
    int find(int x) {
        if (parent[x] == x) {
            return x;
        }
        return parent[x] = find(parent[x]);
    }
    
    void merge(int x, int y) {
        int px = find(x), py = find(y);
        if (px != py) {
            if (rank[px] < rank[py]) {
                parent[px] = py;
            } else if (rank[px] > rank[py]) {
                parent[py] = px;
            } else {
                parent[px] = py;
                ++rank[py];
            }
        }
    }
    
private:
    vector parent;
    vector rank;
};

3. 总结

通过等级合并和路径压缩这两种优化策略，可以显著提高并查集算法的效率。在实际应用中，根据实际情况结合这两种优化策略使用，可以获得更好的效果。