信竞学习笔记：并查集

Tiger

发表于 2026-03-22

更新于 2026-03-22

学习笔记

11 1.6~2.1 分钟 739

本文所述内容不包含扩展域并查集。

1. 并查集

并查集是一种可以快捷、方便地实现集合合并和查找元素操作的数据结构。并查集以树的形式存储。

1.1. 基本实现

并查集的两个最基础的操作是合并两个集合和查找一个元素的根节点。

首先我们要存储并查集，并查集通常存储元素的父节点，如下：

int p[N]; // p[i] 代表第 i 个元素的父节点

for (int i=1; i<=n; i++) p[i] = i; // 初始化，假设所有元素的父节点都是自己，即每个元素都是一个集合

这样，当 p[x] == x 的时候，就可以判定元素 x 是根节点。

在此基础上，我们可以实现两个基本操作：

int Find(int x) {
    while (x != p[x]) x = p[x];
    return x;
}

void Merge(int a, int b) {
    int pa = Find(a), pb = Find(b);
    p[pa] = pb;
}

1.2. 路径压缩

在极端情况下，并查集可能会退化成一条链，所以我们要进行压缩优化，使查找操作性的时间复杂度接近 $O(1)$ ：

int Find(int x) {
    if (x != p[x]) p[x] = Find(p[x]);
    return p[x];
}

void Merge(int a, int b) ; // 合并操作同上

2. 并查集的其他算法

2.1. 统计集合内元素个数

我们可以维护一个 s 数组来统计集合内元素个数。由于每个元素刚开始都是一个集合，所以每个元素初始对应的 s[i] 值都为 1。

在合并集合时，我们要检查 pa 和 pb 是否相等，如果相等，说明二者原本就在同一集合内；如果不相等，则可以合并。 pa 集合成为 pb 集合的下属时，s[pb] 也要对应地加上 s[pa] 。于是，我们得到了如下代码：

// 全局变量
int p[N], s[N]; // p[i] 代表第 i 个元素的父节点

// main 函数内
for (int i=1; i<=n; i++) p[i] = i, s[i] = 1; // 初始化，假设所有元素的父节点都是自己，即每个元素都是一个集合

// main 函数外
int Find(int x) {
    if (x != p[x]) p[x] = Find(p[x]);
    return p[x];
}

void Merge(int a, int b) {
    int pa = Find(a), pb = Find(b);
    if (pa != pb) {
        s[pb] += s[pa];
        p[pa] = pb;
    }
}

int get_size(int x) {
    return s[Find(x)];
}

2.2. 计算同一集合内两个元素之间的距离

我们可以维护一个 d 数组来计算集合内元素到集合根的距离。利用类似于前缀和的思想，两个元素 A、B 之间的距离就等于 A 到根节点的距离减 B 节点到根节点的距离再取绝对值。代码如下：

// 其他内容同上

int d[N];

int get_dis(int a, int b) {
    int pa = Find(a), pb = Find(b);
    if (pa != pb) return -1; // a, b 不在同一集合中，返回 -1
    return max(0, abs(d[a] - d[b]));
}