%%
# 纲要
> 主干纲要、Hint/线索/路标
# Q&A
#### 已明确
#### 待明确
> 当下仍存有的疑惑
**❓<font color="#c0504d"> 有什么问题？</font>**
# Buffer
## 闪念
> sudden idea
## 候选资料
> Read it later
%%
# 并查集
并查集是一种用于**管理 "元素所属集合"** 的**树型**数据结构，其实现为 "**一个==森林==**"——其中**每棵树代表一个集合**，**树中的节点表示 "对应==集合中的元素=="**
并查集主要支持两个基本操作：
- **==查找==**（Find）： **查询某个元素所属集合**（查询对应的树的**根节点**）
- **==合并==**（Union）：**合并两个元素所属集合**（合并对应的树）
<br>
## 并查集操作的时空复杂度
> 由于 `Unite` 是在 `Find` 之后执行常量级别的**父指针修改**，因此 `Union` 操作的时间复杂度同 `Find` 操作。
- 空间复杂度：$O(n)$ ，其中 $n$ 为元素数量。
- 时间复杂度：
- 同时了应用 "**路径压缩** 与 "**按秩合并**" 优化时，单次操作均为 $O(\alpha(n)) \approx O(1)$
- $\alpha()$ 为**阿克曼函数的反函数**（增长极其缓慢）[^1]，单次操作的平均开销**可认为是常数 $O(1)$**。
###### 分析说明
| 优化方式 | 单次操作时间复杂度 | 最坏情况下 $m$ 次操作的时间复杂度 |
| ---------------- | -------------- | -------------------- |
| 无忧化 | $O(n)$ | $O(mn)$ |
| 路径压缩 or 按秩合并（其一） | $O(\log n)$ | $O(m\log n)$ |
| 路径压缩 + 按秩合并 | $O(\alpha(n))$ | $O(m\,\alpha(n))$ |
在没有 "**路径压缩**" 的情况下，由于**树**可能退化为 "**单链**"，因此单次 `Find` 的最坏时间开销可能为 $O(n)$。，因此同为 $O(n)$。
<br>
## 并查集的应用
- **网络连通性方面**；
- **最小生成树（Kruskal 算法）**：用于判断边是否形成环。
- **动态连通性问题**：如社交网络好友关系的合并查询。
- **等式不等式系统**：如 `a == b, b == c, c != d` 类型的判断问题。
#### 网络连通性方面
- 判断**两个节点**是否在连通（是否在**同一连通分量**中）
- 先得到所有 "**连通分量**" 后，再通过 `find` 查询看两节点是否在同一集合中。
- **判断无向图的连通性**：
- 将无向图中的节点作为并查集的元素，若两个节点之间有边相连，则**将它们所属的集合合并**。
- 最终，**若所有节点都属于同一个集合，则图是连通的**；否则，图是非连通的。
- **获取无向图中的所有连通分量**（求连通分量数量）
- **获取有向图中的所有强连通分量**
- 将有向图中的节点作为并查集的元素，从**任意节点**开始进行 DFS，将**已访问节点的父节点**指向 **==同一个根节点==**（可选入口节点所在树的根节点）。
- 搜索结束后，**每个根节点所代表的节点集合就是一个强连通分量**。
- **无向图的环路检测**
- Kruskal 算法中（判断**边加入后是否会成环**）
<br><br>
# 并查集的实现
主要涉及三个部分，其余如 "**删除**" 与 "**移动**" 操作参见[^1]
- （1）**初始化**
- 初始时， **每个元素**均作为**一个==独立集合==** （即对应一棵独立的树, 只有 **==根节点==**）
- 用一个数组记录 "**==每个元素的父节点==**"，初始时记录**各节点的父节点为其自身**。
- （2）**查找**
- 操作：**从给定节点沿着树向上移动**，直至**根节点**，返回根节点。
- 优化：**路径压缩（Path Compression）**——在 `Find` 操作时，将访问路径上的所有节点直接连接到根节点，减少后续查询的层数。
- （3）**合并**
- 操作：合并两棵树，**将一棵树的根节点连接至另一棵树**。
- 优化：**按秩合并（Union by Rank）**——在 `Union` 操作时，总是让 **高度较小的树** 挂到 **高度较大的树** 上，以保持树的高度尽可能小。
> [!caution] "**按秩合并**" 只是 "**尝试合并出最矮的树**" ，并不保证一定最矮。
>
> - **秩**有两种定义：**树的深度**、**树的节点**，取其一即可。
> - 秩代表的 "==**深度**==" 是 "**==深度上界==**" 而不是准确值，因为在路径压缩过程中，树的深度可能会被改变
实现：
```cpp
class UnionFind {
public:
// 初始化并查集
// 初始时, 每个元素均作为一个独立集合(对应一棵独立的树, 只有根节点), 初始化父节点为其自身.
UnionFind(size_t n) : parent(n), rank(n, 1) {
std::iota(parent.begin(), parent.end(), 0); // parent[i] = i;
}
// 查找 (带路径压缩): 自给定节点起向上移动, 直至根节点.
// 路径压缩: 查询过程中经过的每个元素都属于该集合, 将其直连至根节点, 加快后续查询
size_t find(size_t x) {
if (parent[x] != x) {
parent[x] = find(parent[x]); // 路径压缩.
}
return parent[x];
}
// 合并
// 按秩合并: 将"高度较小的树"挂到"高度较大的树"
void unite(size_t x, size_t y) {
x = find(x), y = find(y);
if (x == y) return;
if (rank[x] < rank[y]) std::swap(x, y); // 令y是小树,将y挂到x.
parent[y] = x;
++rank[y];
}
// 判断两元素是否属于同一集合
bool connected(size_t x, size_t y) {
return find(x) == find(y);
}
private:
std::vector<size_t> parent; // 记录每个元素的父节点
std::vector<size_t> rank; // 记录树的秩(深度), 用于按秩合并.
};
```
<br><br>
# 参考资料
- [01. 并查集知识 \| 算法通关手册（LeetCode）](https://algo.itcharge.cn/07.Tree/05.Union-Find/01.Union-Find/#_6-2-%E7%9C%81%E4%BB%BD%E6%95%B0%E9%87%8F)
- [并查集 - OI Wiki](https://oi-wiki.org/ds/dsu/)
- [leetcode.cn/circle/discuss/qmjuMW/](https://leetcode.cn/circle/discuss/qmjuMW/)
# Footnotes
[^1]: [并查集 - OI Wiki](https://oi-wiki.org/ds/dsu/)