【数据结构】并查集

引入

• 【6】并查集 [CCF NOI 大纲（2025 修订版）- 2.2.3.2]

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

并查集

P3367 【模板】并查集

【模板】并查集
请实现一个数据结构，维护以下操作：

• 并：合并 \(x\) 与 \(y\) 所在集合。
• 查：查询 \(x\) 与 \(y\) 是否在同一集合。

并查集模板题。

并查集维护集合的思想是利用集合中的代表元来唯一标识一个集合。

为了便于集合管理，我们可以钦定所有元素的代表元为其本身，其本身单独表示一个集合。该操作是并查集的初始化操作。

考虑并操作，我们需要查询两个元素的代表元并合并之。形式化地，\(f_{f_{x}} = f_{y}\)。我们将该操作命名为 \(\texttt{merge}\)。

接下来我们考虑如何实现查询代表元。引用图论，我们可以按层次依次向上查询根节点，实现一个效率为 \(\Theta(\alpha(n))\) 的查询操作。我们将该操作命名为 \(\texttt{find}\)。

如此，我们可以将 \(\texttt{merge}(x,y)\) 定义为 \(f_{\texttt{find}(x)} \to \texttt{find}(y)\)。

这样我们完成了并查集的朴素实现。

并查集优化

如果我们仅使用朴素算法，当并查集退化成一条链，查询代表元达到最劣复杂度 \(\mathcal{O}(n)\) 的。我们称这种情况为并查集退化。因此我们要在这里考虑分别对 \(\texttt{find}\) 和 \(\texttt{merge}\) 作优化。

路径压缩

这种算法是对 \(\texttt{find}\) 操作作优化。

考虑到 \(\texttt{find}\) 的朴素实现瓶颈在于需要按层次依次向上查询根节点向上处理查询，如果我们能在一次查询过程中作记忆化，考虑一并维护所有代表元为 \(f_{x_i}\) 的节点，在找到代表元后，把它们全部合并给 \(f_{y_i}\)。如此破坏树形结构的层次，直接访问集合的代表元，该优化被称作 路径压缩 Compression。形式化地，\(f_x\gets\texttt{find}(f_{x})\)。

由于路径压缩实现简单，可以快速实现复杂度可以接受的并查集，因此在 OI 中应用广泛。

按秩合并 & 并查集启发式合并

这种算法是对 \(\texttt{merge}\) 操作作优化。

我们容易想到，维护两颗树的合并时，可以将深度较小的子树合并到深度较大的子树上。根据实现的不同，我们把它们称为 按秩合并 Linking by rank 和 并查集启发式合并 Linking by size。

算法复杂度

时间复杂度

本段参考了 Tarjan 的论文^[1] 和 OI-Wiki^[2]。

在此节我们钦定，\(n\) 表示 \(\texttt{merge}\) 操作被执行次数，\(m\) 表示 \(\texttt{find}\) 操作被执行次数。

当 \(m\ge n\) 时

实现方式	朴素 \(\texttt{merge}\)	按秩合并 & 启发式合并
朴素 \(\texttt{find}\)	\(\Theta(mn)\)	\(\Theta(m\log n)\)
路径压缩	\(\Theta(m\log_{(1+m/n)} n)\)	\(\Theta(m\alpha(m,n))\)

当 \(m < n\) 时

实现方式	朴素 \(\texttt{merge}\)	按秩合并 & 启发式合并
朴素 \(\texttt{find}\)	\(\Theta(mn)\)	\(\Theta(n + m\log n)\)
路径压缩	\(\Theta(n + m\log n)\)	\(\Theta(n + m\alpha(m,n))\)

空间复杂度

由并查集需要维护 \(n\) 个元素的代表元可知，并查集的空间复杂度为 \(\Theta(n)\)。

模板代码

struct DSU{
	int N = 1e5 + 10; 
	int f[N];
	void init(int n){for(int i = 1;i <= n;i ++)f[i] = i;}
	int find(int n){return f[x] == x ? x : f[x] = find(f[x]);} // 路径压缩
	bool same(int x,int y){return find(x) == find(y);}
	void merge(int x,int y){if(find(x) != find(y))f[find(x)] = find(y);}
}dsu;

其中 \(N\) 为元素数量。

经典题型

种类并查集

种类并查集用于维护并查集题目中不给出节点所属集合而给出节点关系的情况。

[BOI2003] 团伙

有 \(n\) 个人，给定 \(m\) 对敌友关系，规定朋友的朋友是朋友，敌人的敌人是朋友，朋友之间组团，求团队数。

规定 \(\text{friend}(u,v)\) 表示 \(u\) 与 \(v\) 互为朋友关系，\(\text{enemy}(u,v)\) 表示 \(u\) 与 \(v\) 互为敌人关系，则有

\[\text{enemy}(u_i,v_i) \Leftrightarrow \text{friend}(u_i,v_i + n) \ \text{with}\ \text{friend}(v_i,u_i+n),\ \text{when}\ \text{enemy}(k,k+n) \]

实现上需要注意，因为我们建立的是 \(p\) 与 \(p+n\) 之间的敌友关系，于是为了维护 \(+n\) 节点，我们需要开 \(2\) 倍空间。

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'

int f[2010];

void init(int n) {
	for(int i = 1; i <= n; i++) {
		f[i] = i;
	}
	return ;
}
int find(int x) {
	return f[x] == x ? x : f[x] = find(f[x]);
}
void merge(int x,int y) {
	if(find(x) != find(y))f[find(x)] = find(y);
	return;
}

int main() {
	cin.tie(nullptr),cout.tie(nullptr);
	int n,m;
	cin >> n >> m;

	init(2 * n);
	char ch;
	int x,y;
	for(int i = 1; i <= m; i ++) {
		cin >> ch >> x >> y;
		if(ch == 'F')merge(x,y);
		else {
			merge(y + n,x);
			merge(x + n,y);
		}
	}
	int r = 0;
	for(int i = 1;i <= n;i ++){
		if(f[i] == i)r ++;
	}
	cout << r << endl;
	return 0;
}

带权并查集

带权并查集即在维护并查集合并的过程中，节点本身带有权值的并查集。

例题

[USACO04OPEN] Cube Stacking

给定 \(n\) 个方块，它们独立构成方块柱，试维护：

• 并：将包含方块 \(x\) 的方块柱移动到包含方块 \(y\) 的方块柱上。
• 查：查询方块 \(x\) 在其所在的方块柱中，\(x\) 下面的方块数量。

带权并查集模板题。

考虑如何重构 \(\texttt{find}\)。在路径压缩的基础上，可以考虑 \(x\) 和当前父节点的编号 \(t\)，一并维护节点 \(x\) 的权值。

对于本题，维护的权值即为木块 \(i\) 距离地面的距离（距离地面有几个木块） \(\text{dis}_i\) 和木柱的长度 \(\text{len}_i\)。

重构 \(\texttt{merge}\)。在原合并的基础上，考虑更新 \(x\) 的权值 \(\text{dis}_x\) 加上合并对象 \(y\) 所在木柱的长度。形式化地，\(\text{dis}_x\to\text{dis}_x + \text{len}_y\)；更新 \(y\) 所在木柱的长度为 \(x\) 所在木柱长度与 \(y\) 所在木柱的长度之和。由于 \(x\) 所在木柱已经参与合并，为保证其不对答案参与贡献，把 \(x\) 所在木柱长度归零。形式化地，\(\text{len}_y\to\text{len}_y + \text{len}_x,\text{len}_x\to 0\)。

这样我们就完成了带权并查集的维护。

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'

int f[30010],dis[30010],len[30010]; 
int find(int x) {
    if(f[x] == x) return x;
    else {
        int t = f[x];
        f[x] = find(f[x]);
        dis[x] += dis[t]; // 一并计算权值
        return f[x];
    }
}
void merge(int x,int y){
	int fx = find(x);
	int fy = find(y);
	if(fx != fy){
		f[fx] = fy;
		dis[fx] += len[fy];
		len[fy] += len[fx];
		len[fx] = 0;
	}
	return ;
}
int main(){
	cin.tie(nullptr),cout.tie(nullptr);
	
	int P;
	cin >> P;
	for(int i=1;i<=30000;i++){
		f[i] = i;
		len[i] = 1;
	}
	char ch;
	int x,y;
	for(int i = 1;i <= P;i ++){
		cin >> ch;
		if(ch == 'M'){
			cin >> x >> y;
			merge(x,y);
		}else{
			cin >> x;
			find(x);
			cout << dis[x] << endl;
		}
	}
	
	return 0;
}

一倍经验 [NOI2002] 银河英雄传说 的处理操作如下：

cin >> x >> y;
int fx = find(x);
int fy = find(y);
if(fx != fy)cout << -1 << endl;
else cout << abs(dis[x] - dis[y]) - 1 << endl;

重新发布于 \(2025.7.21\)。

---

1. Tarjan, R. E., & Van Leeuwen, J. (1984). Worst-case analysis of set union algorithms. Journal of the ACM (JACM) ↩︎

2. OI-Wiki，并查集-并查集复杂度 ↩︎