Casey

并查集

最近更新：2025-04-02 | 字数总计：575 | 阅读估时：2分钟 | 阅读量：次

并查集主要解决的是集合上的问题，可以实现将两个集合合并，和查询两个元素是否在一个集合中。

构造

并查集的构造方式为：将一个集合构造为一棵树，树中的节点为集合中的元素，每个节点存储有父节点的指针，根节点为该集合标识且其父节点为自身。并查集的合并操作为可以视作两棵树的合并操作（一棵树作为另一棵树的子树），查询两个元素是否在一个集合中可以通过检查两个元素所在树的根节点是否一致实现。

根据上述的描述，并查集在代码中的实现方式如下。

int parent[N]; // N is the maximum number of elements
int n; // n is the actual number of elements

void init() {
    for (int i = 1; i <= n; i++) {
        parent[i] = i;
    }
}

查找元素所在树的根节点及集合合并操作的代码实现如下。

int find(int x) {
    return parent[x] == x ? x : find(parent[x]);
}

void unite(int x, int y) {
    int rx = find(x), ry = find(y);
    if (rx != ry) {
        parent[rx] = ry;
    }
}

优化

当集合中的元素增多时，查找根节点和集合合并的操作会因树深度的增大而效率降低。针对这一现象，并查集的查找与合并操作需要优化。

路径压缩

路径压缩主要针对查找操作进行优化，每次查找某一元素的根节点时，会将该元素到根节点路径上的所有节点直接连接至根节点，使后续对该元素及路径上的元素查询更快。代码实现如下。

1
2
3

int find(int x) {
    return parent[x] == x ? x : parent[x] = find(parent[x]);
}

按秩合并

按秩合并使用额外的数组秩 rank[] 标识集合树的深度，每次合并时会将较小秩的集合作为子树合并至较大秩的集合。代码实现如下。

int rank[N];
void unite(int x, int y) {
    int rx = find(x), ry = find(y);
    if (rx != ry) {
        if (rank[rx] > rank[ry]) {
            parent[ry] = rx;
        }
        else if (rank[rx] < rank[ry]) {
            parent[rx] = ry;
        }
        else {
            parent[ry] = rx;
            rank[rx]++;
        }
    }
}

注意，此处的 rank[] 为秩的估计值，而非真实值，因此不需要严格的更新因路径压缩产生的变化。

2025-04-02 该篇文章被 Casey 打上标签: 算法 C++ 归为分类: 学习