本周学了并查集和 Kruskal 算法。

并查集

并查集（Disjoint-set data structure，直译为不交集数据结构），用于处理不交集的合并和查询问题。

并查集一般使用数组（线性存储结构） 作为存储方式。

合并：

• 连接两个集合：直接在两树根之间添一条边

查询：

• 找两个元素是否在同一集合：是否为同一祖先

优化：

1. 路径压缩：检测是否为同一集合时记忆化祖先
2. 按秩合并：“秩”小（或大）的是被合并集合。“秩”没有统一定义（可以是树的深度，也可以是树的大小）

Kruskal

Kruskal 算法需要用到并查集，主要思想是贪心

将边数组（比如链式前向星的 $edges$）按边权小（或大）的排序，然后遍历构建树

边两边的节点如果在同一个集合，说明会构成环，不加入最小边权树

树的边总数小于 $n - 1$（$n$ 为点总数）的话，就说明该图是非连通图