README.md

并查集（Disjoint Set）

并查集基础

• 图会用到并查集

• 另一种树形结构

• 连接问题

  网络节点的连接状态

  数学集合的实现

  连接问题比路径问题回答的问题少

• 并查集有两个基本操作

  Union：合并两个子集成为一个新的集合

  Find：查找元素所在集合

• 回答一个问题

  isConnected：元素是否在同个集合

Quick Find

• 实现一个直观的并查集（基于id）

  通过数据的id是否相同判断数据是否在同个集合内

  Union操作的时间复杂度O(n)

  Find操作的时间复杂度O(1)

Quick Union

• 实现一个通用的并查集（基于树）

  每个节点指向父节点（可以用数组实现）

  对于树的根节点，规定其父节点为自己

  时间复杂度跟树的高度相关，树的不断合并可能会使树严重不平衡

基于size的优化（优化有限）

• 将元素少的集合的根节点指向元素多的集合的根节点，从而使树的高度尽量小

• 根据元素的多少判断树的高度并不完全准确

基于rank的优化

• 将高度小的集合的根节点指向高度大的集合的根节点，从而使树的高度尽量小

• rank[i]表示根节点为i的树的高度

• 基于size和基于rank的优化都是针对Union操作

基于路径压缩的优化

• 基于路径压缩的优化针对Find操作

• 在执行Find操作的过程中，将路径上的所有节点都直接连接到根节点上

• 并查集的操作，时间复杂度近乎O(1)

---

参考

1. 算法与数据结构--综合提升篇（c++版）
2. 并查集的C++实现及优化