并查集#

并查集是一种用于处理集合合并和查询的数据结构，常用于连通性问题。它可以动态地添加和合并集合，并快速地查询两个元素是否在同一个集合中。 ————chatGPT

并查集被很多OIer认为是最简洁而优雅的数据结构之一，主要用于解决一些元素分组的问题。它管理一系列不相交的集合，并支持两种操作：

合并（Union）：把两个不相交的集合合并为一个集合。
查询（Find）：查询两个元素是否在同一个集合中。

并查集的时间复杂度主要取决于查找的复杂度，因为合并的复杂度一般较小。一般而言，使用路径压缩和按秩合并的优化方法，可以使单次操作的时间复杂度达到 O(log n)。

基本代码#

数据

1
int fa[MAXN]; //代表节点的父节点

初始化

1
inline void init(int n)
2
{
3
    for (int i = 1; i <= n; ++i)
4
        fa[i] = i;
5
    // 初始状态所有节点的父节点都是它自己
6
}

关于inline函数，看这里 ~~（留个坑，以后有空讲讲）~~

查询

1
int find(int x)
2
{
3
    if(fa[x] == x)
4
        return x;
5
    else
6
        return find(fa[x]);
7
}

合并

1
inline void merge(int i, int j)
2
{
3
    fa[find(i)] = find(j);
4
}

优化#

并查集的优化主要包括路径压缩和按秩合并两种方法。

1. 路径压缩

在查找一个元素所在的集合时，可以将路径上的所有节点都直接连接到根节点上，这样可以使得后续的查找操作更快。路径压缩的实现方法：

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

2. 按秩合并

这种优化方法也叫加权标记法，在合并两个集合时，可以比较它们的深度(也叫秩)，将深度较小的集合连接到深度较大的集合上，这样可以减少树的深度，提高操作效率。按秩合并的实现方法：

初始化

1
inline void init(int n)
2
{
3
    for (int i = 1; i <= n; ++i)
4
    {
5
        fa[i] = i;
6
        rank[i] = 1;
7
    }
8
}

合并

1
inline void merge(int i, int j)
2
{
3
    int x = find(i), y = find(j);    //先找到两个根节点
4
    if (rank[x] <= rank[y])
5
        fa[x] = y;
6
    else
7
        fa[y] = x;
8
    if (rank[x] == rank[y] && x != y)
9
        rank[y]++;
10
        //如果深度相同且根节点不同，则新的根节点的深度+1
11
}