并查集type
status
date
slug
summary
tags
category
icon
password
Property
并查集（Union Find）：一种树型的数据结构，用于处理一些不交集（Disjoint Sets）的合并及查询问题。不交集指的是一系列没有重复元素的集合。
并查集主要支持两种操作：
- 合并（Union）：将两个集合合并成一个集合。
- 查找（Find）：确定某个元素属于哪个集合。通常是返回集合内的一个「代表元素」。
简单来说，并查集就是用来处理集合的合并和集合的查询。
- 并查集中的「集」在这里指的是不相交的集合，即一系列没有重复元素的集合。
- 并查集中的「并」指的就是集合的并集操作，将两个集合合并之后就变成一个集合。合并操作如下所示：
- 并查集中的「查」是对于集合中存放的元素来说的，通常需要查询两个元素是否属于同一个集合
如果只是想知道一个元素是否在集合中，可以通过
Python 或其他语言中的 set 集合来解决。而如果想知道两个元素是否属于同一个集合，则仅用一个 set 集合就很难做到了。这就需要用到「并查集」结构。定义一下「并查集」结构所支持的操作接口：
- 合并
union(x, y)：将集合x和集合y合并成一个集合。
- 查找
find(x)：查找元素x属于哪个集合。
- 查找
is_connected(x, y)：查询元素x和y是否在同一个集合中。
并查集的两种实现思路
快速查询：基于数组实现
如果希望并查集的查询效率高一些，那么就可以侧重于查询操作。
在使用「快速查询」思路实现并查集时，可以使用一个「数组结构」来表示集合中的元素。数组元素和集合元素是一一对应的，可以将数组的索引值作为每个元素的集合编号，称为
id。然后可以对数组进行以下操作来实现并查集：- 当初始化时：将每个元素的集合编号初始化为数组下标索引。则所有元素的
id都是唯一的，代表着每个元素单独属于一个集合
- 合并操作时：需要将其中一个集合中的所有元素
id更改为另一个集合中的id，这样能够保证在合并后一个集合中所有元素的id均相同
- 查找操作时：如果两个元素的
id一样，则说明它们属于同一个集合；如果两个元素的id不一样，则说明它们不属于同一个集合
举个例子来说明一下，使用数组来表示一系列集合元素
{0}, {1}, {2}, {3}, {4}, {5}, {6}, {7}，初始化时如下图所示。从下图中可以看出：元素的集合编号就是数组的索引值，代表着每个元素属于一个集合。
当进行一系列的合并操作后，比如合并后变为
{0}, {1, 2, 3}, {4}, {5, 6}, {7}，合并操作的结果如下图所示。从图中可以看出，在进行一系列合并操作后，下标为 1、2、3 的元素集合编号是一致的，说明这 3 个 元素同属于一个集合。同理下标为 5 和 6 的元素则同属于另一个集合。
在快速查询的实现思路中，单次查询操作的时间复杂度是，而单次合并操作的时间复杂度为（每次合并操作需要遍历数组）。两者的时间复杂度相差得比较大，完全牺牲了合并操作的性能。因此，这种并查集的实现思路并不常用
快速合并：基于森林实现
因为快速查询的实现思路中，合并操作的效率比较低。所以重点是提高合并操作的效率。
在使用「快速合并」思路实现并查集时，可以使用「一个森林（若干棵树）」来存储所有集合。每一棵树代表一个集合，树上的每个节点都是一个元素，树根节点为这个集合的代表元素。
注意：与普通的树形结构（父节点指向子节点）不同的是，基于森林实现的并查集中，树中的子节点是指向父节点的。
此时，仍然可以使用一个数组
fa 来记录这个森林。用fa[x] 来保存 x 的父节点的集合编号，代表着元素节点 x 指向父节点 fa[x]。当初始化时，
fa[x] 值赋值为下标索引x。每个节点都构成了一棵树，即每个节点都是一个根节点：在进行合并操作时，只需要将两个元素的树根节点相连接（
fa[root1] = root2）即可。而在进行查询操作时，只需要查看两个元素的树根节点是否一致，就能知道两个元素是否属于同一个集合。find函数，一个while搞定：
当调用
find(5)时，按照的路径到达根节点，最终返回 1。基于
find(x)函数，实现merge(u,v)也很简单：通过find函数找到的根节点。如果两者的根节点不相同，则将的父节点设为。如果相同，则无需任何操作。
调用
merge(8, 5)时：- 先通过
find(8),find(5)找到对应的根节点7和1
- 再将
fa[7]修改为1
对数组
fa 进行以下操作来实现并查集：- 当初始化时：将每个元素的集合编号初始化为数组
fa的下标索引。所有元素的根节点的集合编号不一样，代表着每个元素单独属于一个集合
- 合并操作时：需要将两个集合的树根节点相连接。即令其中一个集合的树根节点指向另一个集合的树根节点（
fa[root1] = root2），这样合并后当前集合中的所有元素的树根节点均为同一个
- 查找操作时：分别从两个元素开始，通过数组
fa存储的值，不断递归访问元素的父节点，直到到达树根节点。如果两个元素的树根节点一样，则说明它们属于同一个集合；如果两个元素的树根节点不一样，则说明它们不属于同一个集合
举个例子来说明一下，使用数组来表示一系列集合元素
{0}, {1}, {2}, {3}, {4}, {5}, {6}, {7}，初始化时如下图所示。从下图中可以看出：元素的集合编号就是数组 fa 的索引值，代表着每个元素属于一个集合。
当进行一系列的合并操作后，比如
union(4, 5)、union(6, 7)、union(4, 7) 操作后变为 {0}, {1}, {2}, {3}, {4, 5, 6, 7}，合并操作的步骤及结果如下图所示。从图中可以看出，在进行一系列合并操作后，fa[4] == fa[5] == fa[6] == fa[fa[7]]，即 4、5、6、7 的元素根节点编号都是 4，说明这 4 个 元素同属于一个集合。
路径压缩
在集合很大或者树很不平衡时，使用上述「快速合并」思路实现并查集的代码效率很差，最坏情况下，树会退化成一条链，单次查询的时间复杂度高达。并查集的最坏情况如下图所示。
为了避免出现最坏情况，一个常见的优化方式是「路径压缩」。
路径压缩（Path Compression）：在从底向上查找根节点过程中，如果此时访问的节点不是根节点，则可以把这个节点尽量向上移动一下，从而减少树的层树。这个过程就叫做路径压缩。
路径压缩有两种方式：一种叫做「隔代压缩」；另一种叫做「完全压缩」。
隔代压缩
在查询时，两步一压缩，一直循环执行「把当前节点指向它的父亲节点的父亲节点」这样的操作，从而减小树的深度。
完全压缩
在查询时，把被查询的节点到根节点的路径上的所有节点的父节点设置为根节点，从而减小树的深度。也就是说，在向上查询的同时，把在路径上的每个节点都直接连接到根上，以后查询时就能直接查询到根节点。
相比较于「隔代压缩」，「完全压缩」压缩的更加彻底。
- 第一个 while：找到 x 所在树的根节点 r
- 第二个 while：将 x → r 路径上的所有节点的fa更新为r
按秩合并
因为路径压缩只在查询时进行，并且只压缩一棵树上的路径，所以并查集最终的结构仍然可能是比较复杂的。为了避免这种情况，另一个优化方式是「按秩合并」。
按秩合并（Union By Rank）：指的是在每次合并操作时，都把「秩」较小的树根节点指向「秩」较大的树根节点。
这里的「秩」有两种定义，一种定义指的是树的深度；另一种定义指的是树的大小（即集合节点个数）。无论采用哪种定义，集合的秩都记录在树的根节点上。
按秩合并也有两种方式：一种叫做「按深度合并」；另一种叫做「按大小合并」。
按深度合并
在每次合并操作时，都把「深度」较小的树根节点指向「深度」较大的树根节点。
用一个数组
rank 记录每个根节点对应的树的深度（如果不是根节点，其 rank 值相当于以它作为根节点的子树的深度）。初始化时，将所有元素的
rank 值设为 1。在合并操作时，比较两个根节点，把 rank 值较小的根节点指向 rank 值较大的根节点上合并。
按大小合并
这里的大小指的是集合节点个数。在每次合并操作时，都把「集合节点个数」较少的树根节点指向「集合节点个数」较大的树根节点。
用一个数组
size 记录每个根节点对应的集合节点个数（如果不是根节点，其 size 值相当于以它作为根节点的子树的集合节点个数）。初始化时，将所有元素的
size 值设为 1。在合并操作时，比较两个根节点，把 size 值较小的根节点指向 size 值较大的根节点上合并。
并查集的题目
省份数量
题目：有
n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。省份是一组直接或间接相连的城市，组内不含其他没有相连的城市。给你一个
n x n 的矩阵 isConnected ，其中isConnected[i][j] = 1表示第i个城市和第j个城市直接相连，而isConnected[i][j] = 0表示二者不直接相连。返回矩阵中省份的数量。示例：
最长连续序列
题目：给定一个未排序的整数数组
nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。请设计并实现时间复杂度为 O(n) 的算法解决此问题。示例：