【并查集】并查集学习笔记

explore

首先，因为论坛域名永久修改的那个通知我没注意到（往常都是 301 跳转），所以这两个月死活回不到论坛

预备

本文将对 并查集 这一概念做最浅显的解释，以及其在 OI 中的常用模板，预计阅读时间 10 分钟

阅读本文前请确保对于 森林、树、节点、叶子、元素 等基本数据结构有一定了解

代码可能因为和 BBCode 的部分关键词（如 加粗 等冲突，导致代码中有部分被错误渲染为 加粗 或 倾斜，而 i、b 等被吞掉）
同步发于小蒟蒻的 Github：https://github.com/Estrella-Explore/OI-notes


总述

并查集 是一种用于管理元素所属集合的数据结构，实现为一个森林，其中每棵树表示一个集合，树中的节点表示对应集合中的元素。——OI Wiki

以上是 oi-wiki.org 对于并查集这一概念的总述（显然不讲人话）

我们可以这样理解：并查集 是一种数据结构，主要作用是用来管理一些元素间的联系关系（当然有时你也可以把 并查集 当作一种思想）

如果还不懂，可以打个浅显的比方：

kkk、粉兔、CZ 等等一些人都拜师学习武功，问题是武功有许多门派，大小门派之间有的还是分支关系，在有的情况下门派还会合并，这时处理这些人之间的派系关系就变得十分复杂，而 并查集 就是用来解决这种问题的方法

详细讲解

支持的操作

最基础的 并查集 支持两种操作：

• 查找元素所属的集合（下文 find() 函数）
• ---（由此操作，你可以扩展一下，得到判断两元素是否在同一集合的函数 in_same_tree()）
• 两集合的合并（下文 merge() 函数）
  

（注：本文只讲解 OI 中常见的操作，对于 启发式合并 等不涉及）

思想介绍

对于一个有宗教信仰的人，如果你问 Ta 信什么教，Ta 可能会回答“拜上帝会天主教”，然而你还是弄不懂，于是 Ta 又回答“新教”——属于“基督教”，于是你知道 Ta 是一个基督教徒而不是穆斯林

这是一种 并查集 思想的体现——使用一个节点（或一个元素），来代表整棵树（或整个集合）

这里十分重要，务必好好理解：


寻找元素所属集合，只要找父节点和根节点就知道了；

如果两元素在同一集合中，那么祖先节点一定相同；

如果两集合要合并，只要令其有共同祖先即可


仔细想想，你会觉得这种思想似乎很符合直觉，或者说很简洁优雅，的确，它被众多 OIer 认为是最优雅的算法之一（而且板子还很短，十分好理解）

算法实践

初始化

首先，我们有若干个元素等待处理（下文中抽象为叶子），此时其间的所属关系尚未确立

[C++] 纯文本查看 复制代码

const int MAX = 114514; // 节点的数量，可修改，这里是 OI 中一种常见的方法，不推荐在真正工作中这么写
int dsu[MAX];           // 这里使用数组存储节点的父节点，索引代表节点编号
// 有的板子使用结构体，大同小异，但在基础并查集操作中使用数组就够了

为了统一，可以把这些元素的祖先节点设为自己，于是所有元素构成的集合成为了一片深度为 1 的森林

[C++] 纯文本查看 复制代码

/*初始化*/
void dsu_init()
{
    for (int i = 0; i < MAX; i++)
    {
        dsu[i] = i; // 父节点设为自己
    }
}

查询操作

这里给一种递归的写法，如果自己是根节点就返回自己，否则再次查找父节点的祖先，直至查询到根节点 注：有点板子使用三目运算符，看个人喜好，我一般只在压行时使用

[C++] 纯文本查看 复制代码

/*传入节点 index，找到根节点*/
int find_basic(int a)
{
    if (a == dsu[a])
    {
        return a;
    }
    else
    {
        return find_basic(dsu[a]);
    }
    // 很简单的递归，如果自己是根节点就返回自己，否则再次查找父节点的祖先
}

合并操作（基础）

两集合要合并，就必须有共同祖先。

最简单的方法是直接选择其中一棵树，将其根节点作为一个普通节点，父节点设为另一棵树的根节点

[C++] 纯文本查看 复制代码

/*传入两棵树的根节点，以最直接方式合并这两棵树*/
void merge(int a, int b)
{
    dsu[b] = a;
}

可能的问题——退化



如上图，有的时候树会退化为链表，造成复杂度提升，而大多数时候我们只需要查找元素是否在同一集合

于是我们可以把该链表改写成在该情景下等效的树：




路径优化

听起来很唬人，实际上在每次查询时顺手把节点连至根节点即可

[C++] 纯文本查看 复制代码

/*带路径优化的查找，入参为节点 index，返回祖先 index*/
int find(int a)
{
    return dsu[a] == a ? a : dsu[a] = find(dsu[a]);
    if (a == dsu[a])
    {
        return a;
    }
    else
    {
        dsu[a] = find_basic(dsu[a]);
        return dsu[a];
    }
}

未完待续……

模板

[C++] 纯文本查看 复制代码

// dsu_temple.cpp
// author:Estrella_Explore
// time 2023/12/14 12:00

#include <iostream>
using namespace std;
const int MAX = 114514; // 节点的数量，可修改，这里是 OI 中一种常见的方法
int dsu[MAX];           // 这里使用数组存储节点的父节点，索引代表节点编号
// 有的板子使用结构体，大同小异，但在基础并查集操作中使用数组就够了

/*初始化*/
inline void dsu_init()
{
    for (int i = 0; i < MAX; i++)
    {
        dsu[i] = i; // 父节点设为自己
    }
}

/*传入节点 index，找到根节点*/
int find_basic(int a)
{
    if (a == dsu[a])
    {
        return a;
    }
    else
    {
        return find_basic(dsu[a]);
    }
    // 很简单的递归，如果自己是根节点就返回自己，否则再次查找父节点的祖先
}

/*带路径优化的查找，入参为节点 index，返回祖先 index*/
int find(int a)
{
    if (a == dsu[a])
    {
        return a;
    }
    else
    {
        dsu[a] = find_basic(dsu[a]);
        return dsu[a];
    }
}

/*传入两棵树的根节点，以最直接方式合并这两棵树*/
inline void merge(int a, int b)
{
    dsu[b] = a;
}

int main()
{
    // freopen("xxx.in", "r", stdin);
    // freopen("xxx.out", "w", stdout);
    /*
     * ios::sync_with_stdio(0);
     * cin.tie(0);// 调代码的时候记得注释这两行，会造成 stream 和传统 IO 顺序混乱
     */
    // -----------------------------------------
    dsu_init();

    /*You code here.*/

    // -----------------------------------------
    // fclose(stdin);
    // fclose(stdout);
    return 0;
}