C++并查集详解（从零开始掌握并查集数据结构）

并查集的基本实现（C++）

最简单的并查集可以用一个数组 parent[] 来表示，其中 parent[i] 表示元素 i 的父节点。初始时，每个元素的父节点是自己。

#include <iostream>#include <vector>using namespace std;class UnionFind {private:    vector<int> parent;public:    // 构造函数：初始化并查集    UnionFind(int n) {        parent.resize(n);        for (int i = 0; i < n; ++i) {            parent[i] = i; // 每个元素初始指向自己        }    }    // 查找 x 所在集合的根节点    int find(int x) {        if (parent[x] != x) {            return find(parent[x]);        }        return x;    }    // 合并 x 和 y 所在的集合    void unite(int x, int y) {        int rootX = find(x);        int rootY = find(y);        if (rootX != rootY) {            parent[rootX] = rootY;        }    }    // 判断 x 和 y 是否在同一集合    bool connected(int x, int y) {        return find(x) == find(y);    }};

路径压缩优化

上面的实现虽然正确，但效率不高。例如，在一条长链中查找根节点可能需要 O(n) 时间。为了提升性能，我们可以使用路径压缩（Path Compression）技术。

路径压缩的思想是：在 find 操作时，将路径上的所有节点直接连接到根节点，从而扁平化树结构。

// 优化后的 find 函数（带路径压缩）int find(int x) {    if (parent[x] != x) {        parent[x] = find(parent[x]); // 递归压缩路径    }    return parent[x];}

按秩合并优化

除了路径压缩，我们还可以使用按秩合并（Union by Rank）来进一步优化。所谓“秩”，可以理解为树的高度。合并时，总是将较小的树接到较大的树下面，避免树变得过高。

class UnionFind {private:    vector<int> parent;    vector<int> rank; // 记录每个节点的“秩”public:    UnionFind(int n) {        parent.resize(n);        rank.resize(n, 0);        for (int i = 0; i < n; ++i) {            parent[i] = i;        }    }    int find(int x) {        if (parent[x] != x) {            parent[x] = find(parent[x]);        }        return parent[x];    }    void unite(int x, int y) {        int rootX = find(x);        int rootY = find(y);        if (rootX != rootY) {            // 按秩合并            if (rank[rootX] < rank[rootY]) {                parent[rootX] = rootY;            } else if (rank[rootX] > rank[rootY]) {                parent[rootY] = rootX;            } else {                parent[rootY] = rootX;                rank[rootX]++;            }        }    }    bool connected(int x, int y) {        return find(x) == find(y);    }};

应用场景举例

并查集广泛应用于以下场景：

• 判断图中是否存在环（Kruskal 最小生成树算法）
• 社交网络中的好友关系合并
• 岛屿数量问题（LeetCode 经典题）
• 动态连通性问题

总结

通过本教程，你已经掌握了 C++ Union-Find 的基本原理、代码实现以及两种关键优化方法。只要记住：路径压缩 + 按秩合并，就能让并查集的操作接近常数时间复杂度（阿克曼函数的反函数）。

现在，你可以自信地在算法题或项目中使用并查集教程中学到的知识了！动手写一写代码，加深理解吧。

提示：在实际面试或竞赛中，并查集往往是解决连通性问题的“秘密武器”，务必熟练掌握！