disjoint-set(不相交集合)数据结构,也称为 union-find 数据结构或 merge-find set,是一种跟踪集合划分为多个不重叠子集的数据结构。它提供近乎常数时间的操作来添加新集合、合并现有集合以及确定元素是否在同一集合中。底层算法使用两种主要技术 Union by Rank(按秩合并)和 Path Compression(路径压缩)来实现高效的 时间复杂度。每个元素表示为一个节点,每个不相交集合组形成一个树结构。不相交集合在许多图算法中很有用,例如 Kruskal 算法等。
用自己的话写下这一站的结论。