【数据结构 | 并查集】维护元素分组信息，支持高效合并集合、查询元素所在集合

文章目录

• 并查集
• • 概述
  • 引入
• 并查集的实现
• • 存储方式
  • Union-Find抽象基类
  • 两种实现思路
  • 基本实现
  • • 基于Quick Find思路
    • 基于 Quick Union 思路
  • 优化
  • • 基于 size 的优化
    • 基于 rank 的优化
  • find优化
  • • 路径压缩
    • 路径分裂
    • 路径减半
• 总结

并查集

概述

并查集（Disjoint Set Union，简称并查集），也叫不相交集合（一系列没有重复元素的集合），是一种用于处理集合的数据结构。

并查集主要专注于两个核心操作：

1. 查找（Find）：

• 查找操作可用于确定一个元素属于哪个子集。
• 通常返回一个代表该子集的元素，称为代表元素（或者说根元素）。

2. 合并（Union）：

• 合并操作用于将两个子集合并成一个。
• 将两个元素连接到一起，那么这两个元素所在的集合就合并为一个集合，此时的操作是先找到这两个元素的代表元素，再将某个子集的代表元素连接到另一个子集的代表元素上。

引入

并查集是为了有效地解决集合合并和查询问题而设计的数据结构。

我们来看这样一个问题，假设现在有n个村庄，有些村庄之间有连接的路，有些村庄之间并没有连接的路：

现在需要设计这样一个数据结构，能够快速执行两个操作：

• 查询2个村庄之间是否有连接的路
• 连接两个村庄

此时，我们就可以利用并查集来解决这个问题，两个核心操作如下：

1. 查询操作： 使用并查集的Find操作，可以迅速确定两个村庄是否属于同一个集合，即它们之间是否有连接的路。如果两个村庄具有相同的代表元素，它们在同一个集合中，表示它们之间有连接的路；如果代表元素不同，则表示它们之间没有连接。

2. 合并操作： 使用并查集的Union操作，可以将两个村庄所在的集合合并为一个集合，表示它们之间建立了连接的路。通过将一个集合的代表元素链接到另一个集合的代表元素上实现。

在这里，每个村庄对应一个并查集的节点，最初每个节点自成一个集合。如果采用数组、链表、平衡二叉树或者集合(Set)来实现，查询和连接的复杂度都是O(n)，使用并查集的复杂度是O(logn)，可以优化至O(α(

标签：查集,int,元素,find,parents,集合,节点
From： https://blog.csdn.net/m0_62999278/article/details/137564625