【数据结构】并查集

• 并查集是一种树形的数据结构，用于处理集合相关的问题。
  • 通常集合中的元素都不具备层次关系，而是因为共通的性质而被划分在一起。
  • 当存在多个集合，而又需要判断任意两个元素是否处在同一个集合中时，就需要使用并查集来维护集合元素之间的关系。
• 并查集有两个主要的操作：
  1. 合并操作：将两个子集合并成一个子集。
  2. 查找操作：确定某个元素处在哪个集合。
• 一般用固定大小的数组来实现并查集，但可以用森林的模型来解释并查集的操作。【森林即多棵树】
  • 假设题目中元素只有 m 个，则并查集底层只需维护一个 m 大小的数组 parent 即可。【parent 数组保存对应元素的父节点】
  • 对于合并操作的解释：将两个元素合并在同一个子集，就相当于将两棵树合并成一棵树。
  • 对于查找操作的解释：要确定两个元素处于同一个集合只需要确定两个元素是否处于同一棵树即可。

• 并查集的实现非常简洁。

  • 初始化：设置每个元素为一个集合，即设置每个元素的父节点为自己。

    for(int i = 0; i < parent.size(); ++i)
      parent[i] = i;
    

  • 查找：找到元素所在集合的根，即所在树的根。【从代码中看出，find 函数会递归调用，直到找到集合的根】【此处的 find 函数已经进行路径压缩，简单来说，就是把当前搜索路径上的所有元素都连接到最顶部的根上去，这样每一棵树的高度都不会过分高】

    int find(int x) // 找root
    {
        if(parent[x] != x) parent[x] = find(parent[x]); // 路径压缩，此处可以用 while 语句来实现路径压缩的非递归版本
        return parent[x];
    }
    

  • 合并：分别找出两个元素的根进行连接即可。

    void union(int x, int y)
    {
        parent[find(x)] = find(y);
        return;
    }
    

• 可以通过下述例子来加深理解。

  1. 假设有 5 个元素，则初始化一个大小为 5 的 parent 数组：

  2. 假设元素 0 和元素 1 有关系，则调用 union(0, 1)，注意此时 find(0) 或 find(1) 都是简单地返回 0 或 1：

  3. 假设元素 0 分别和元素 2 、元素 3 有关系，则分别调用 union(2, 0) 和 union(3, 0)，注意 find(0) 会返回 1：

• 最后要提及的是关于并查集的一些优化：

  • 可以注意到，上面例子的最后结果中留下了两棵树（即两个集合），其中 root 1 体型较大，root 4 体型较小，如果后续调用 union(1, 4) 则会把大树放置到小树底下（这样显然是不够平衡的），然而调用 union(4, 1) 就会避免前面的情况。【这样说明了不同的参数调用顺序会给 union 带来不同的结果】
  • 有两种优化思路，一种是 with size，一种是 with rank。
  • 简单来说，with size 方法就是并查集中维护一个 size 数组（记录元素所在树的大小），在 union 操作中进行更新；同理，with rank 方法就是维护一个 rank 数组（记录元素所在树的高度），同样是在 union 操作中进行更新。

• 并查集实现如下：

class DSU // 并查集
{
public:
    vector parent;
    DSU(int N) : parent(N)
    {
        // parent = vector(N);
        for(int i = 0; i < N; ++i) parent[i] = i;
    }
    int find(int x) // 找root
    {
        if(parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }
    void _union(int x, int y)
    {
        parent[find(x)] = find(y);
        return;
    }
};

• 并查集 with size 实现如下：

class DSU // 并查集 with size
{
public:
    vector parent;
    vector size;
    DSU(int N) : max_size(1), parent(N), size(N, 1)
    {
        for(int i = 0; i < N; ++i) parent[i] = i;
    }
    int find(int x) // 找root
    {
        if(parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }
    void union(int x, int y)
    {
        // parent[find(x)] = find(y);
        int px = find(x), py = find(y);
        if(px == py) return;
        if(size[px] <= size[py])
        {
            parent[px] = py;
            size[py] += size[px];
        }
        else
        {
            parent[py] = px;
            size[px] += size[py];
        }
        return;
    }
};

• 并查集 with rank 实现如下：

class DSU // 并查集 with rank
{
public:
    vector parent;
    vector rank;
    DSU(int N) : parent(N), rank(N)
    {
        for(int i = 0; i < N; ++i) parent[i] = i;
    }
    int find(int x) // 找root
    {
        if(parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }
    void _union(int x, int y)
    {
        int px = find(x), py = find(y);
        if(px == py) return;
        if(rank[px] < rank[py])
            parent[px] = py;
        else if(rank[px] > rank[py])
            parent[py] = px;
        else
        {
            parent[py] = px;
            ++rank[px];
        }
        return;
    }
};

• leetcode - 305.岛屿数量 Ⅱ（会员题）
• leetcode - 547.省份数量
• leetcode - 128.最长连续序列
• luogu - P1551.亲戚
• luogu - P1536.村村通