并查集Union-Find-algorithm

6mhR2IbK7THsk3a

并查集（Union-Find）是一种用于处理动态连通性问题的数据结构。它通常用来处理像网络连通性、集合合并等问题。并查集操作高效，尤其适用于需要频繁进行合并和查询的情景，具有接近常数时间复杂度。

以下是对并查集的详细解释，包括它的基本概念、实现步骤，以及C++代码示例。

1.并查集的基本概念

并查集的主要功能有两个：

查找（Find）：确定某个元素属于哪个集合。
合并（Union）：将两个元素所在的集合合并为一个集合。

并查集通常通过树结构实现，每个元素都指向它的父节点，通过这种方式可以追溯到树的根节点。

父节点（Parent）：并查集中每个元素有一个指向其父节点的指针。
根节点（Root）：在并查集中，一个集合可以看作是一棵树的形式，根节点是整个树的代表元素。

优化策略

为了提高并查集操作的效率，通常会使用以下两个重要的优化技巧：

路径压缩（Path Compression）：在执行查找操作时，将访问的节点直接连接到根节点，以减少树的深度。
按秩合并（Union by Rank 或 Union by Size）：在合并两个集合时，将规模较小的集合连接到规模较大的集合下，避免形成深树。

2.实现步骤

1. 初始化

使用一个数组 parent 来表示每个元素的父节点，初始时每个元素都是自己的父节点。
使用一个数组 rank 来记录每棵树的高度，以便于在合并时按秩合并。

2. 查找（Find）

查找时，通过递归找到根节点，并在路径上将所有节点直接连接到根节点（路径压缩）。

3. 合并（Union）

合并时，通过比较两个集合的秩来决定将哪个集合连接到另一个集合上（按秩合并）。

C++代码实现

基础班

class UnionFind {
public:
    // 初始化并查集
    UnionFind(int n) {
        parent.resize(n);
        for (int i = 0; i < n; ++i) {
            parent[i] = i;  // 初始时，每个元素都是自己的父节点
        }
    }

    // 查找根节点（无路径压缩）
    int find(int x) {
        while (x != parent[x]) {
            x = parent[x];
        }
        return x;
    }

    // 合并两个集合（无按秩合并）
    void unionSets(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            parent[rootY] = rootX;
        }
    }

    // 检查两个元素是否属于同一个集合
    bool isConnected(int x, int y) {
        return find(x) == find(y);
    }

private:
    vector<int> parent;  // 父节点数组
};

优化版

#include <iostream>
#include <vector>

using namespace std;

class UnionFind {
public:
    // 初始化并查集
    UnionFind(vector<int> nums) {
        for (int i = 0; i < nums.size(); ++i) {
            parent[nums[i]] = nums[i];  // 初始时，每个元素都是自己的父节点
            rank[nums[i]]=1;
        }
    }

    // 查找根节点并进行路径压缩
    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);  // 递归查找根节点并进行路径压缩
        }
        return parent[x];
    }

    // 合并两个集合
    void unionSets(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);

        if (rootX != rootY) {
            // 按秩合并，将秩小的树合并到秩大的树下
            if (rank[rootX] > rank[rootY]) {
                parent[rootY] = rootX;
            } else if (rank[rootX] < rank[rootY]) {
                parent[rootX] = rootY;
            } else {
                parent[rootY] = rootX;
                rank[rootX]++;
            }
        }
    }

    // 检查两个元素是否属于同一个集合
    bool isConnected(int x, int y) {
        return find(x) == find(y);
    }

private:
    unordered_map<int,int> parent;  // 父节点数组
    unordered_map<int,int> rank;    // 树的高度数组，用于优化合并操作
};

int main() {
    // 假设有10个元素，编号为0到9
    vector<int>nums={0,1,2,3,4,5,6,7,8,9}
    UnionFind uf(nums);

    // 合并一些集合
    uf.unionSets(1, 2);
    uf.unionSets(2, 3);
    uf.unionSets(4, 5);
    uf.unionSets(6, 7);
    uf.unionSets(3, 7);

    // 检查连通性
    cout << "1 和 7 是否连通: " << (uf.isConnected(1, 7) ? "是" : "否") << endl;
    cout << "4 和 6 是否连通: " << (uf.isConnected(4, 6) ? "是" : "否") << endl;

    return 0;
}

代码讲解

类定义和初始化：
- UnionFind(int n): 初始化大小为 n 的并查集，每个节点都是自己的父节点，初始秩为1。
- parent 数组用于存储每个节点的父节点。
- rank 数组用于存储树的高度，优化合并。
查找操作：
- find(int x): 使用递归实现查找并进行路径压缩。路径压缩将每次查找的节点直接连接到根节点，显著减少后续查找操作的时间。
合并操作：
- unionSets(int x, int y): 查找 x 和 y 的根节点，如果根节点不同则按秩合并。将高度较小的树连接到较大的树上，保证树的高度尽量保持较低。
检查连通性：
- isConnected(int x, int y): 判断 x 和 y 是否属于同一个集合，通过比较它们的根节点是否相同来实现。