并查集基本思想

一句话理解

并查集维护“谁和谁在同一集合”。

为什么要学

代码短，非常重要。

讲解

支持合并两个集合、查询是否同一集合。不能轻易拆开。

例子

朋友圈：认识就 merge，问两个人是否间接认识。

常见错误

• 需要删边还用朴素并查集。
• 没路径压缩也没按秩，退化成链。