并查集

字数

823 字

阅读时间

4 分钟

---

一、作用

1. 合并两个集合
2. 查询某个元素的祖宗节点

二、优化

1. 路径压缩（最常用），时间复杂度为 $O(\log n)$ ，最坏为 $O(n)$

路径压缩写法：
int find(int x)
{
	if (p[x] != x) p[x] = find(p[x]);
	return p[x];
}
不压缩写法：
int find(int x)
{
	if (p[x] != x) find(p[x]);
	return p[x];
}

相比之下，路径压缩后，每次查询的时间复杂度为 O(1)，比不进行路径压缩的时间复杂度要更好

1. 按秩合并：合并集合时，每次将节点个数/树深度较少的合并到深度大的树中，时间复杂度为 $O(\log n)$，用得不多
2. 两者结合的优化，时间复杂度最优，为 $O(\alpha (n))$

• 凡是可以用并查集的题目，这两者的优化做法都可以看作是 $O(1)$ 的实践复杂度

三、扩展

1. 记录每个集合的大小
   • 将集合大小的属性绑定到根节点
2. 记录每个点到根节点的距离
   • 距离属性需要绑定到每个元素上

四、处理

并查集初始化不要忘记：
int main()
{
	for (int i = 1; i <= n; i ++) p[i] = i; // p 数组是并查集
}

• 使用并查集遇到二维（如：迷宫、九宫格等）时，可将二维转换为一维（坐标的映射），即：$(x,y)\to x\ast n+y$
  • 前提：$x,y$ 都需要从 0 开始

注意！！！

如果在并查集合并时需要同时合并并查集中点的数量，或是并查集总价值等等，需要将所有点的累加到祖宗节点处

假设：遇到两个不同并查集时，将其合并
int a, b;
cin >> a >> b; // 输入两个点
int pa = find(a), pb = find(b); // pa 和 pb 分别是 a 和 b 所在并查集的祖宗节点
if (pa != pb) // 如果是两个不同的并查集，则合并
{
	p[pa] = pb; // 将 pa 并查集并入 pb 并查集中 
	// 或可写为：p[pa] = p[pb]； 这两种写法没有区别
	size[pb] += size[pa]; // size 数组存储的是并查集中的点的数量
}

五、对并查集的理解

将两个并查集合并完成后，即：

int pa = find(a), pb = find(b);
if (pa != pb) p[pa] = pb; // 将 pa 并查集合并到 pb 并查集中

则此时这两者的关系如图： root 就是 pb 并查集的根节点 pb，若在下一次查询时，find(x) 的 x 是原 pa 并查集，则其根节点为 p[x]，也即：原 pa，所以在查询时会进入 if 判断

int find(int x)
{
	if (p[x] != x) p[x] = find(p[x]); // 进入此判断
	return p[x];
}

由于在合并时，已经执行了 p[pa] = pb，即：将 pa 指向了 pb，故原 pa 并查集中，只有原根节点 pa 指向了 pb，故每当原 pa 并查集中的元素进行find 查询时，都会先指向 pa，再由pa 执行find 指向 pb，再由路径压缩 p[x] = find(p[x]) 进行更新，由该元素直接指向 pb

贡献者

freeway348

文件历史

最后编辑于 4 天前查看完整历史

6442b-WWWW

e6f15-DisjointSetUnion

4ab72-ma1