[Note] 并查集理论

[L4] 并查集

本篇是并查集的理论部分，只负责回答“并查集是什么、什么时候用、为什么能用、基础代码怎么写”。

具体题型、完整模板和例题放在 并查集题型整理。

学习顺序按下面这条线走：

概念 $\to$ 地位 $\to$ 用途 $\to$ 核心原理 $\to$ 代码实现

1. 概念：并查集是什么

并查集是一种用来维护若干个互不相交集合的数据结构。

它关心的不是集合内部每个点怎么排列，而是每个点属于哪个集合。

为了表示一个集合，它会给每个集合选出一个代表元，也就是这个集合的根。

最基础的并查集支持三类操作：

1. find(x)：找到 $x$ 所在集合的代表元。
2. merge(x, y)：把 $x$ 所在集合和 $y$ 所在集合合并。
3. same(x, y)：判断 $x,y$ 是否属于同一个集合。

所以并查集最基本的语言是：

如果 find(x) == find(y)，那么 $x,y$ 处在同一个集合里。

在图论里，这个集合通常就是一个连通块；在关系题里，这个集合通常表示“已经被推出来必须等价的一批对象”。

2. 地位：它在知识体系里算什么

并查集是维护连通性和等价关系的基础工具。

它的地位有点像图论里的“维护器”：它通常不单独决定答案，而是在别的策略中负责维护某种集合状态。

常见搭配有：

1. Kruskal：按边权排序，靠并查集判断加边是否成环。
2. 离线处理：把不好维护的删除操作倒过来，变成添加操作。
3. 二分答案：每次 check(mid) 用并查集判断是否连通或阻断。
4. 贪心排序：按权值顺序加入约束，靠并查集判断第一次矛盾。
5. 差值约束：用带权并查集维护点与点之间的相对值。

并查集的长处是 合并，短处是 分裂。

如果题目要求在线删边、删点，并且不能离线倒序处理，普通并查集通常不够，需要可撤销并查集、线段树分治、动态树等更强的结构。

3. 用途：看到什么题可以想到并查集

3.1 维护连通块

如果题目反复出现“合并两个集合” “判断两个点是否连通” “统计连通块数量”，可以先考虑普通并查集。

这类题的核心变量通常是：cnt 当前连通块数量；每成功合并两个不同连通块，就让 cnt--。

对应题型：并查集题型整理 | P1955、P1783、P1197。

3.2 离散关系建模

如果题目出现「朋友 / 敌人」「同类 / 异类」「吃 / 被吃」这类关系，并且关系可以沿着链条传递，可以考虑扩展域并查集。

扩展域的做法不是让并查集直接理解“敌人”或者“捕食”，而是把一个点拆成多个域，再把关系翻译成“哪些域应该连在一起”。

对应题型：并查集题型整理 | P1892、P1525、P2024 三倍域写法。

3.3 维护相对值

如果题目给出的是 $val[x] - val[y] = w$ 这类关系，或者可以转化成这种关系，可以考虑带权并查集。

这里并查集不只判断连通，还要在同一个集合内查询两个点之间的差值。

常见形式有：

1. 模意义下的关系：例如食物链，维护 $(val[x] - val[y]) \bmod 3$。
2. 真实势能差：例如区间和，维护 $pre[r] - pre[l - 1] = s$。

对应题型：并查集题型整理 | P2024 带权写法、P2294。

3.4 整体合并模型

如果题目不是把两个点合并，而是把一个集合整体接到另一个集合后面，就要注意合并方向。

这类题通常还要维护集合内的相对位置，比如某个元素到队头的距离、两个元素之间隔了多少个元素。

对应题型：并查集题型整理 | P1196、P5092。

3.5 集合属性维护

如果题目只需要连通块结构，但答案依赖每个集合的属性，就可以在根节点上维护额外信息。

常见属性包括：

1. 集合大小。
2. 集合内边数。
3. 权值和。
4. 最大值 / 最小值。

对应题型：ZJ2020I 这类把对象建成图，再统计连通块属性的题。

4. 核心原理：并查集为什么能用

4.1 代表元

并查集用一棵树表示一个集合，树根就是集合的代表元。

fa[x] 表示 $x$ 的父亲。如果 fa[x] == x，说明 $x$ 是当前集合的根。

find(x) 的作用就是沿着父亲指针一路向上，找到这个根。

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

只要两个点最后找到的根相同，就说明它们已经被合并进同一个集合。

4.2 路径压缩

如果每次 find 都沿着链往上爬，树可能会变得很深，查询就会变慢。

路径压缩做的事情是：在查找根的同时，把路径上的点直接挂到根上。

这不会改变集合关系，只是把树压扁，让之后的查询更快。

4.3 按大小合并

合并两个集合时，通常把小集合挂到大集合下面。

这样可以尽量避免树高增长，使并查集的复杂度接近常数。

if( siz[rx] > siz[ry] ) swap( rx, ry );
fa[rx] = ry;
siz[ry] += siz[rx];

这里的 siz[] 只在根节点上有意义，表示当前集合大小。

4.4 等价关系

普通并查集本质上维护的是一种等价关系。这个关系满足：

1. 自己和自己等价。
2. 如果 $a$ 和 $b$ 等价，那么 $b$ 和 $a$ 等价。
3. 如果 $a$ 和 $b$ 等价，$b$ 和 $c$ 等价，那么 $a$ 和 $c$ 等价。

这就是为什么它适合处理“相等”“同类”“在同一个连通块中”这类关系。

但如果关系不是简单等价关系，就需要改造模型：

1. 对立关系：拆成二倍域。
2. 三元循环关系：拆成三倍域，或者压成模 $3$ 带权关系。
3. 差值关系：用带权并查集维护相对值。

4.5 合并方向是否有意义

普通并查集中，merge(x, y) 谁挂谁通常不影响答案。

但下面几类题不能随便交换方向：

1. 带权并查集：根节点接谁会影响 dis[root] 的维护公式。
2. 队列合并：题目规定了“哪一列接到哪一列后面”。
3. 指定根语义：有些题要求编号小的当领袖，或者人数多的当根。

所以写题时要先判断：这次合并只是“两个集合合成一个”，还是“一个集合以特定方向接到另一个集合上”。

5. 代码实现：基础模板

理论页只放最基础的并查集模板。扩展域、带权并查集、队列模型放在 并查集题型整理 里统一维护。

▶

基础并查集

#include <bits/stdc++.h>
using namespace std;

const int maxn = 2e5 + 5;

// 并查集：路径压缩 + 按大小合并
struct DSU {
/* ======================================== */
int fa[maxn], siz[maxn];
void init( int N ) { for( int i = 1; i <= N; ++ i ) fa[i] = i, siz[i] = 1; }
int find( int x ) { return fa[x] == x ? x : fa[x] = find( fa[x] ); }
bool merge( int x, int y ) {
    int rx = find( x ), ry = find( y );
    if( rx == ry ) return 0;
    if( siz[rx] > siz[ry] ) swap( rx, ry );
    fa[rx] = ry, siz[ry] += siz[rx];
    return 1;
}
bool same( int x, int y ) { return find( x ) == find( y ); }
int size( int x ) { return siz[find( x )]; }
/* ======================================== */
} dsu;

5.1 常用写法

维护连通块数量：

int cnt = n;
if( dsu.merge( x, y ) ) cnt --;

判断是否连通：

if( dsu.same( x, y ) ) {
    // x, y 在同一个连通块
}

离散化后使用：

int dx = disc.get_idx( x );
int dy = disc.get_idx( y );
dsu.merge( dx, dy );

6. 检查表

遇到并查集题时，可以按这个顺序判断：

1. 题目是否在维护集合、连通块、同类关系？
2. 操作主要是合并，还是删除？如果是删除，能不能倒着做？
3. 编号值域是否过大？是否需要离散化？
4. 是否只需要判断连通，还是还要维护相对关系？
5. 关系是否是同类 / 异类？如果是，考虑二倍域。
6. 关系是否是三元循环？如果是，考虑三倍域或模 $3$ 带权并查集。
7. 是否出现 $val[x] - val[y] = w$？如果是，考虑带权并查集。
8. 合并方向是否有实际意义？如果有，不能无脑按大小合并。
9. 根节点是否需要维护集合属性？如果需要，合并时同步更新。

7. 实战入口

• 主实战整理页：并查集题型整理

• 暂时独立保留：ZJ2020I Invoking the Magic，之后如果整理“属性维护 / 连通块建模”，再合并进去。