如何用C++实现带路径压缩的并查集算法优化连通性快速判定逻辑

并查集是一种用于管理不相交集合的数据结构，核心功能包括查询两个元素是否属于同一集合、合并两个集合，在图连通性判定、社交网络关系分析、最小生成树构建等场景中有广泛应用。基础的并查集实现查找根节点时可能产生较长的链结构，导致时间复杂度偏高，而路径压缩优化可以在查找过程中将节点的父节点直接指向根节点，大幅缩短后续查找的路径长度。

并查集核心原理

并查集通常用数组来存储每个元素的父节点，初始时每个元素的父节点指向自身，代表每个元素都是独立的集合。两个核心操作分别是find查找根节点和union合并集合：

• find(x)：查找元素x所在集合的根节点，路径压缩优化就在这个操作中实现
• union(x, y)：将元素x和元素y所在的集合合并，通常将其中一个集合的根节点指向另一个集合的根节点

带路径压缩的C++实现源码

以下是完整的优化版并查集实现，包含初始化、查找、合并和连通性判定四个核心方法：

#include <iostream>
#include <vector>
using namespace std;

class UnionFind {
private:
    vector<int> parent;  // 存储每个元素的父节点
    vector<int> rank;    // 存储每个集合的秩，用于优化合并逻辑，避免树过高
    int count;           // 当前独立集合的数量

public:
    // 初始化并查集，n为元素总数
    UnionFind(int n) {
        count = n;
        parent.resize(n);
        rank.resize(n, 0);
        // 初始时每个元素的父节点指向自身
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }

    // 带路径压缩的查找操作，返回元素x的根节点
    int find(int x) {
        // 如果当前节点的父节点不是自身，递归查找父节点的根节点，并将当前节点的父节点直接指向根节点
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }

    // 合并元素x和元素y所在的集合
    void unite(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        // 如果根节点相同，说明已经属于同一集合，不需要合并
        if (rootX == rootY) {
            return;
        }
        // 按秩合并，将秩较小的树合并到秩较大的树上，避免树的高度过高
        if (rank[rootX] < rank[rootY]) {
            parent[rootX] = rootY;
        } else if (rank[rootX] > rank[rootY]) {
            parent[rootY] = rootX;
        } else {
            // 秩相等时，任意合并，合并后目标树的秩加1
            parent[rootY] = rootX;
            rank[rootX]++;
        }
        // 合并后独立集合数量减1
        count--;
    }

    // 判断元素x和元素y是否属于同一集合
    bool isConnected(int x, int y) {
        return find(x) == find(y);
    }

    // 返回当前独立集合的数量
    int getCount() {
        return count;
    }
};

// 测试示例
int main() {
    // 初始化5个元素的并查集
    UnionFind uf(5);
    // 合并0和1
    uf.unite(0, 1);
    // 合并1和2
    uf.unite(1, 2);
    // 判定0和2是否连通
    cout << "0和2是否连通: " << (uf.isConnected(0, 2) ? "是" : "否") << endl;
    // 判定0和3是否连通
    cout << "0和3是否连通: " << (uf.isConnected(0, 3) ? "是" : "否") << endl;
    // 合并3和4
    uf.unite(3, 4);
    cout << "当前独立集合数量: " << uf.getCount() << endl;
    return 0;
}

算法复杂度分析

未优化的并查集find操作最坏时间复杂度为O(n)，而加入路径压缩和按秩合并优化后，find和union操作的平均时间复杂度接近O(1)，严格来说是阿克曼函数的反函数级别，在实际应用中可以认为是常数时间，非常适合处理大规模数据的连通性判定场景。

实际应用场景

该优化版并查集可以应用在多个实际开发场景中：

• 图论中的连通分量统计，比如判断一个无向图有多少个连通子图
• 最小生成树算法中的边筛选，比如Kruskal算法中判断加入边是否会形成环
• 社交网络中判断两个用户是否存在间接好友关系
• 动态连通性问题，比如网络连接中判断两个节点是否可达

C++并查集路径压缩连通性判定union_find修改时间：2026-07-06 20:33:23