并查集

并查集的概念

并查集是一种用于处理集合合并与查找问题的数据结构。它提供查找（Find）和合并（Merge）两个基本操作。通过维护树形结构，每个树代表一个集合，通过路径压缩和按秩合并等优化，提高查找和合并操作的效率。常用于解决图论、连通性和最小生成树等问题。

简单来说，并查集就是一种能够处理连通性问题的数据结构。

并查集的引入

假如现在世界上有很多个人，现在设定一个规矩，两个人可以通过比试的输赢来建立一个帮派，赢的就是帮主（如果一个人打败了一个帮派的帮主，那么他就是新帮主，如果只是打败小弟，则需要继续往上,打最早击败过小弟的人），长久如此，通过比试次数越多，帮派就会壮大起来。

现在有 $8$ 个人，他们每一个人都有一个帮派，所以他们现在属于自己的帮派，帮主也是自己。

然后我们假如一个数组 $p$ ,每一个 $p[i]$ 代表的就是打败第 $i$ 位的人，在树形结构里面就是第 $i$ 位人的父节点。

一开始，每个人的$p[i]$ 都是自己，所以图中的边也是指向自己的。
img
之后我们安排 $[1]$ 和 $[2]$ 比试， 然后 $[2]$ 获得胜利，所以这个时候 就变成了 $[1]$ 号的 $p[1] = 2$,关系图就变成 $[1]$ 的边会指向 $[2]$ :
img
之后我们分别安排

  • $[4]$ 和 $[8]$ 比试，$[4]$ 获胜
  • $[5]$ 和 $[6]$ 比试，$[5]$ 获胜
  • $[5]$ 和 $[7]$ 比试，$[5]$ 获胜
  • $[1]$ 和 $[3]$ 比试, $[3]$ 获胜,这个时候$[3]$还要和$[2]$比试，因为$[2]$是帮主,但是这个时候 $[3]$ 输给了 $[2]$
    img

可以看到现在世界上已经有三个帮派(帮主首位)了，分别是:

  • $[2,1,3]$
  • $[4,8]$
  • $[5,6,7]$
    这时 $p$ 数组的值是
  • $p[1] = 2$
  • $p[2] = 2$
  • $p[3] = 2$
  • $p[4] = 4$
  • $p[5] = 5$
  • $p[6] = 5$
  • $p[7] = 5$
  • $p[8] = 4$

现在如果给 $[7]$ 和 $[3]$ 安排一场比试，$[3]$ 赢了，但是还没结束, $[3]$ 还要和最早打败了 $[7]$ 的人比试，即为 $[5]$,之后 $[3]$ 输了,$[5]$ 自然要和$[2]$ 比试一场，之后 $[2]$ 获胜，$[5]$ 带着他帮派的所有人加入 $[2]$ 的麾下。
img

然后就此世界上就只剩下两个帮派了。

并查集的两种操作

首先我们把上面的故事抽象一下，可以发现有两步操作，分别是输了之后，找第一次打败自己的人来继续挑战，然后是比试。

第一种我们可以看做是查找,找帮主，每一个节点都有一个父节点，也正对应了$p[k]$数组。
第二种我们可以看做是合并，两个集合之间的合并。

查找

查找操作用于确定一个元素属于哪个集合，即找到该元素所在集合的代表元素（根节点）。
查找操作的目的是判断两个元素是否属于同一个集合，通过比较它们的根节点来实现。

合并

合并操作用于将两个不相交的集合合并成一个新的集合。
具体操作通常是将其中一个集合的根节点连接到另一个集合的根节点上，从而形成一个新的集合。

朴素版

对于代码的编写，有朴素版，不过我们一般不会采用这种方式，因为效率比较低 $O(n)$

初始化

初始化主要是初始化 $p[k]$ 数组，初始化就是让每个人的父节点都为自己。

1
2
3
4
5
int p[N];
void init()
{
    for(int i=1;i<=n;++i) p[i] = i;
}

查找

通过递归来找根节点

1
2
3
4
5
int find(int x)
{
    return p[x] == x ? x : find(p[x]);
}

合并

只要 $x$ 和 $y$ 不属于同一集合，就需要合并

1
2
3
4
5
6
7
8
bool merge(int x,int y)
{
    x = find(x);
    y = find(y);
    if(x == y) return false;
    p[y] = x;
    return true;
}

路径压缩

路径压缩的思想是在查找操作中，将查找路径上的每个节点都直接连接到根节点。这样，即使树的高度很大，任何一次查找操作都会使路径上的每个节点都直接指向根节点。这种操作会在实际查找的同时，通过修改树的结构，使得未来的查找操作变得更加高效。

大概就是在$find$的过程中，改变这个节点否父节点，最终让所有节点直接指向根节点。
路径压缩前:
img
经过路径压缩后:
img

其实就是改一下 $find$ 函数,写法不唯一。

查询的时间复杂度近乎为$O(1)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
int p[N];
void init()
{
    for(int i=1;i<=n;++i) p[i] = i;
}

int find(int x)//递归1版
{
    return (p[x] != x) ? (p[x] = find(p[x])) : p[x];
    
}
int find(int x)//递归2版
{
    return p[x] = (p[x] == x ? x : find(p[x]));
}
int find(int x)//循环版
{
    while(p[x] != x) x = p[x] = p[p[x]];
    return x;
}

bool merge(int x,int y)
{
    x = find(x);
    y = find(y);
    if(x == y) return false;
    p[y] = x;
    return true;
}

按秩合并

在朴素版本的并查集中，合并操作简单地将一个集合的根节点连接到另一个集合的根节点上。然而，这样的操作可能会导致一些集合的树深度增加，形成不平衡的树。这种情况下，查找操作可能会变得较慢，因为树的高度会增加。

按秩合并的基本思想是在合并操作时，将深度（秩）较小的树合并到深度较大的树上。这样可以避免形成过深的树，保持树的平衡，进而提高查找和合并操作的效率。通常，每个节点都会维护一个秩的信息，表示以该节点为根的树的深度。

所以我们引入一个新的数组 $rnk[i]$ 代表第 $i$ 节点的高度。

这个优化只体现在merge操作上面

查询的时间复杂度为$O(logn)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int p[N],rnk[N];
void init()
{
    for (int i = 1; i <= n; ++i) p[i] = i;
}

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

bool merge(int x, int y)
{
    x = find(x);
    y = find(y);
    if (x == y) return false;
    if (rnk[y] > rnk[x]) swap(x, y);//保证 x 的高度 >= y
    if (rnk[x] == rnk[y]) rnk[x]++;
    p[y] = x;
    return true;
}

启发式合并(通过大小)

通过大小的启发式合并是一种并查集优化策略，它基于集合大小（元素个数）来决定两个集合的合并方式。该启发式合并方法的核心思想是将元素较少的集合合并到元素较多的集合中，以保持树的平衡。

通过这样的合并策略，较小的树被合并到较大的树中，从而避免了形成过深的树。这有助于降低查找操作的时间复杂度，使得树的高度保持在相对较小的范围内，提高了整个并查集的效率。

所以我们引入一个新的数组 $siz[i]$ 代表第 $i$ 个集合的大小,注意的一点是,$siz[i]$ 只在根节点是有效的。

这个优化只体现在merge操作上面

查询的时间复杂度为$O(logn)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int p[N],siz[N];
void init()
{
    for (int i = 1; i <= n; ++i) p[i] = i,siz[i] = 1;//注意这里siz数组要初始化为1
}

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

bool merge(int x, int y)
{
    x = find(x);
    y = find(y);
    if (x == y) return false;
    if (siz[y] > siz[x]) swap(x, y);//保证 x 的集合数量大小 >= y
    p[y] = x;
    siz[x] += siz[y];
    return true;
}

这三种优化都是我们平常经常写的优化方式，不过最常用的应该是路径压缩，毕竟代码更加简洁。但是在$Tarjan$的论文中，证明了只使用路径压缩的最坏复杂度为$O(mlogn)$，不过这种数据我们一般不会遇到，除非出题人水平很高，然后专门出数据卡并查集。所以三种方式都需要掌握，三种优化方式是可以混用的。

封装模板

借鉴的是jls的板子，稍有改动。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
struct DSU
{
    std::vector<int> p, siz;
    DSU() {}
    DSU(int n) { init(n); }
    void init(int n)
    {
        p.resize(n);
        std::iota(p.begin(), p.end(), 0);
        siz.assign(n, 1);
    }
    int find(int x)
    {
        while (x != p[x])
        {
            x = p[x] = p[p[x]];
        }
        return x;
    }
    bool same(int x, int y) { return find(x) == find(y); }
    bool merge(int x, int y)
    {
        int px = find(x);
        int py = find(y);
        if (px == py)
        {
            return false;
        }
        siz[px] += siz[py];
        p[py] = px;
        return true;
    }
    int size(int x) { return siz[find(x)]; }
};

题目

P3367 【模板】并查集 - 洛谷

拓展

带权并查集
算法
#algorithm #并查集 #图论 #数据结构
并查集
http://pikachuxpf.github.io/posts/c517589e/
作者
Pikachu_fpx
发布于
2024年1月12日
许可协议