并查集

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

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

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

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

基本代码

• 数据

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

• 初始化

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

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

• 查询

int find(int x)
{
    if(fa[x] == x)
        return x;
    else
        return find(fa[x]);
}

• 合并

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

优化

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

• 1. 路径压缩

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

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

• 2. 按秩合并

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

• 初始化

inline void init(int n)
{
    for (int i = 1; i <= n; ++i)
    {
        fa[i] = i;
        rank[i] = 1;
    }
}

• 合并

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

• 综合使用路径压缩和按秩合并可以达到最优的时间复杂度，即单次操作的时间复杂度为 O(log n)。

参考文献：

算法学习笔记(1) : 并查集 - 知乎 (zhihu.com)

算法与数据结构—— 并查集_酱懵静的博客-CSDN博客

通俗易懂地讲解《并查集》 - 知乎 (zhihu.com) python文献