# 并查集基础问题
- 「并查集」是一个很有意思的数据结构，但它不是绝大多数公司算法面试和笔试的考点，如果你不感兴趣或者只是冲着面试和笔试学习算法，完全可以不学习；
- 「并查集」是竞赛考点，属于高级数据结构，本身很有意思，但是并不是绝大多数公司面试和笔试的考点，如果时间有限，且对算法与数据结构不感兴趣，完全可以跳过。但不排除少数面试官和公司会考这个数据结构；
- 我自己觉得「并查集」的设计思想是很有趣、且浅显的。难的只是这些问题。如果你有时间、有兴趣，还是很建议学习一下；
- 并查集知识点的 视频讲解 在第 990 题和第 399 题的视频题解里，如果大家看文字觉得枯燥，可以先看看这两个题解的视频。
基础且常见的问题有：
「并查集」进阶问题有：
| 题号 | 链接 | 题解 |
|---|---|---|
| 945 | 使数组唯一的最小增量 (opens new window)（中等） | 文字题解 (opens new window) |
| 399 | 除法求值 (opens new window)（中等） | 视频题解 (opens new window) |
| 685 | 冗余连接 II (opens new window)（困难） | |
| 721 | 账户合并 (opens new window)（中等） | |
| 765 | 情侣牵手 (opens new window)（困难） | |
| 952 | 按公因数计算最大组件大小 (opens new window)（困难） | 文字题解 (opens new window) |
# 参考资料
基础部分：
- 《算法》（第 4 版）第 1 章第 5 节：案例研究：union-find 算法（有关于复杂度的证明）
- 《算法导论》第 21 章：用于不相交集合的数据结构（有关于复杂度的证明）
- AlgoWiki 关于「并查集」 (opens new window)的章节
进阶部分：
- 《算法竞赛进阶指南》（李煜东著）
- 知乎问答：为什么并查集在路径压缩之后的时间复杂度是阿克曼函数?（有论文）
- OI Wiki 关于「并查集」 (opens new window)的章节（有关于复杂度的证明）
温馨提示：「并查集」是一个很有意思的数据结构，但它不是绝大多数公司算法面试和笔试的考点，如果你不感兴趣或者只是冲着面试和笔试学习算法，完全可以不学习。
# 视频讲解
我在 2021 年春季给「力扣」录制过很多题「并查集」的视频，讲解风格与我其它视频的讲解风格一致。如果不想看文字教程的朋友，可以观看视频进行学习。
其中下面两个视频的一开始，我都介绍了并查集的基础知识。
- 「力扣」第 990 题：等式方程的可满足性（中等），视频地址见下表；
- 「力扣」第 399 题：除法求值（中等），视频地址见下表。
这两节的内容非常重要，我花了很多时间制作这两个视频，相信会对大家理解「并查集」的设计思想有所帮助。
说明：发在「力扣」和「B 站」的视频是一样的，发在「力扣」的视频下面还有我编写的文字题解。
如果对「并查集」感兴趣的朋友可以做一下「力扣」并查集 题单 (opens new window)。
作者：liweiwei1419 链接：https://suanfa8.com/union-find 来源：算法吧 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。